Задачи оптимизации перебора вариантов

Сообщение №8205 от - 10 июля 2003 г. 14:12
Тема: Задачи оптимизации перебора вариантов


Отклики на это сообщение:

Здравствуйте!

Я по работе столкнулся со следующей задачей.

Представьте себе спичечный коробок. Он состоит из коробочки и надевающейся на неё крышки. Так вот представьте, что есть m коробочек разной длины и n крышечек тоже разной длины.
Длины коробочек и крышечек заранее не известны, линейки нет. Померить, налезает ли крышка на коробку можно только (!) попробовав надеть.

Можно надевать на одну коробку несколько крышек и засовывавать в одну крышку несколько коробок.

Требуется все коробки покрыть крышками (или доказать, что нельзя), за наименьшее число сравнений.

Кто-нибудь может натолкнуть меня на мысль, как решать эту задачу? Что почитать. нигде такого не видел. Минимизация сравнений вообще актуальна только в сортировке, а здесь не то...


Ну и как в данном случае оптимизировать? Сомневаюсь, что можно сделать меньше, чем за экспоненциальное число сравнений. А мне нужно линейное (в идеале). Пусть даже иногда покрытие не находит.
Что именно почитать по моему случаю?


> Представьте себе спичечный коробок. Он состоит из коробочки и надевающейся на неё крышки. Так вот представьте, что есть m коробочек разной длины и n крышечек тоже разной длины.
> Длины коробочек и крышечек заранее не известны, линейки нет. Померить, налезает ли крышка на коробку можно только (!) попробовав надеть.

> Можно надевать на одну коробку несколько крышек и засовывавать в одну крышку несколько коробок.

> Требуется все коробки покрыть крышками (или доказать, что нельзя), за наименьшее число сравнений.

> Кто-нибудь может натолкнуть меня на мысль, как решать эту задачу? Что почитать. нигде такого не видел. Минимизация сравнений вообще актуальна только в сортировке, а здесь не то...

Рассмотрим такой часный случай:
Пусть есть m коробок, суммарной длины s. И две крышки длины s/2 каждая. Требуется ответить на вопрос: есть решение или нет?

Эта задача является NP-полной. Следовательно, и ваша исходная задача NP-полна - даже в формулировке: есть решение или нет. А минимизация числа сравнений - тем более.


Я согласен, что получение точного ответа, есть решение или нет - NP-полная задача. Но есть ли какое-нибудь эвристическое решение, позволяющее с большой вероятностью получить решение, если оно есть, при этом производя наименьшее (по возможности) количество сравнений.
Например, если расположить коробки и крышки в два ряда, и надевать на коробки крышки (пока влезает) слева направо, то вероятность построения покрытия будет 60% за линейное число сравнений.
Есть ли алгоритм лучше?


Люди добрые, помогите. С института припоминается задача комивояжера - определение кратчайшего пути между точками. Поставлена задача - разработать автоматически маршрут передвижения торгового представителя по торговым точкам с учетом времени работы торговой точки. У кого есть какие-то алгоритмы решения этой задачи или что-нибуть по этой теме, помогите, пожалуйста.
28 февраля 2004 г. 11:05:


Интересует ли кого-нибудь из обитающих здесь заявленный сабж? Если да, то у меня есть нечто, напоминающее простое и понятное доказательство этой теоремы. Нужен трезвый взгляд и умная критика.
10 марта 2004 г. 19:14:



> Интересует ли кого-нибудь из обитающих здесь заявленный сабж? Если да, то у меня есть нечто, напоминающее простое и понятное доказательство этой теоремы. Нужен трезвый взгляд и умная критика.
> 10 марта 2004 г. 19:14:
> Интересует. Вышлите, пожалуйста, Ваше доказательство на мой e-mail: plusskin2@yandex.ru Отвечу обязательно.


> Интересует ли кого-нибудь из обитающих здесь заявленный сабж? Если да, то у меня есть нечто, напоминающее простое и понятное доказательство этой теоремы. Нужен трезвый взгляд и умная критика.
> Получил Ваше доказательство и проанализировал его. Обнаружены пробелы. Более подробный анализ выслал письмом на Ваш e-mail.
plusskin2@yandex.ru


Небольшая история и очень сложная задача с подводным камнем

Задача про шашки.
Есть шахматно-шашечная доска и есть 6 шашек. Каждая из которых может быть либо дамкой либо шашкой, либо белой, либо чёрной. Шашки можно ставить только на чёрные клетки (их 32). Нужен алгоритм, который бы позволил пронумеровать все возможные позиции, которые можно поставить на доске из этих шести шашек. Это нужно для того, чтобы поместить результаты их разыгрывания в базу данных. Вернее алгоритмов нужно два. Один - который по позиции определяет её номер в базе данных. Второй - которой по номеру в базе, выдаёт саму позицию (номера шести клеток и что на них стоит).


А теперь о подводном камне в задаче.

Всё, что написано выше - я сделал, но как выяснилось плохо. Дело в том, что когда шашка доходит до дамочного поля, она становится дамкой. То есть белые шашки не могут стоять на восьмой горизонтали, а чёрные шашки не могут стоять на первой горизонтали. Когда я писал алгоритм, то на эту тонкость не стал обращать внимания, чтобы не усложнять задачу. И база получилась просто несколько большего размера, за счёт этих невозможных позиций. А тут на днях, я решил выяснить, а насколько именно база больше. Посчитал и ужаснулся. Оказывается, что из 3,7 миллиарда позиций, 1,2 миллиарда - невозможные. То есть лишний объём огромный, и конечно же хотелось бы от него избавиться. Но вот как ... . Думал я думал, переписывал алгоритм, переписывал, пытался, пытался. Ничего не получается. Слишком сложно для меня. Видать без высшего математического образования не разберёшься. Но ведь и задача сама по себе не такая уж и тривиальная, чем и интересна. Может быть кто-нибудь сталкивался с подобными или знает как такое решать ?
09 мая 2004 г. 02:36:


> Вернее алгоритмов нужно два. Один - который по позиции определяет её номер в базе данных. Второй - которой по номеру в базе, выдаёт саму позицию (номера шести клеток и что на них стоит).

[...]

> Оказывается, что из 3,7 миллиарда позиций, 1,2 миллиарда - невозможные.

А зачем нужна сплошная нумерация? Почему бы не хранить возможные позиции в хеш-таблице (и, соответственно, индексировать их значением некоторого хэша). В качестве хэша можно использовать хотя бы ту самую сплошную нумерацию всех позиций, а невозможные позиции будут просто отсутствовать в таблице.


> А зачем нужна сплошная нумерация? Почему бы не хранить возможные позиции в хеш-таблице (и, соответственно, индексировать их значением некоторого хэша). В качестве хэша можно использовать хотя бы ту самую сплошную нумерацию всех позиций, а невозможные позиции будут просто отсутствовать в таблице.

Признайтесь, вы не математик ? Потому, что для настоящего математика поиск решения сложной задачи - это удовольствие. Я сам был по уши счастлив, когда написал свой алгоритм. Только вот проблема шашек на дамочных полях - это похоже уже за гранью моей компетенции, потому и решил спросить здесь, у профессионалов.

По поводу хэша - умножте 2,5 миллиарда на 4 байта ( размер нумерации ) и вы узнаете сколько это будет занимать на диске. Это куда больше чем те лишние 1,2 миллиарда, которые есть сейчас.


>

Есть такая задачка, школьная. По дну реки проложен кабель, а в нем 128 проводов. Все провода одного цвета. У монтера есть лодка и простейший тестер - отвертка с лампочкой, показывает наличие напряжения(фазы). К одному берегу подходит линия электропередач. Т.е. имеется источник напряжения. Вот. Задача состоит в том что надо "прозвонить" кабель", т.е. определить концы всех проводов. Сколько раз придется монтеру переплыть реку? Какое наименьшее количество таких ходок вы можете предложить?


> > А зачем нужна сплошная нумерация? Почему бы не хранить возможные позиции в хеш-таблице (и, соответственно, индексировать их значением некоторого хэша). В качестве хэша можно использовать хотя бы ту самую сплошную нумерацию всех позиций, а невозможные позиции будут просто отсутствовать в таблице.

> Признайтесь, вы не математик ?

Совсем даже наоборот. За плечами магистерская диссертация по математике. ;)

> Потому, что для настоящего математика поиск решения сложной задачи - это удовольствие.

Эта задача отнюдь не сложная, а я бы сказал, нудная. Сводится к перебору некоторого количества случаев (например, 28 случаев занумерованных парами (x,y), где x - количество белых шашек, y - количество черных шашек, x+y<=6).
В каждом случае задача аналогична той, что Вы уже решили.

> Я сам был по уши счастлив, когда написал свой алгоритм.

Число всех позиций (и возможных и невозможных) C(32,6)*4^6 = 3711762432
Алгоритм прямо следует из этой формулы: сначала нумераются все сочетания из 32 по 6, а затем всевозможные расстановки номиналов: белая/черная шашка/дамка.

> По поводу хэша - умножте 2,5 миллиарда на 4 байта ( размер нумерации ) и вы узнаете сколько это будет занимать на диске. Это куда больше чем те лишние 1,2 миллиарда, которые есть сейчас.

Так Вы же ничего не сказали о размере записи для конкретной позиции. Скажем, если она 100 байт, то способ с хеш-таблицей будет очень даже экономным.


> > > А зачем нужна сплошная нумерация? Почему бы не хранить возможные позиции в хеш-таблице (и, соответственно, индексировать их значением некоторого хэша). В качестве хэша можно использовать хотя бы ту самую сплошную нумерацию всех позиций, а невозможные позиции будут просто отсутствовать в таблице.

> > Признайтесь, вы не математик ?

> Совсем даже наоборот. За плечами магистерская диссертация по математике. ;)

> > Потому, что для настоящего математика поиск решения сложной задачи - это удовольствие.

> Эта задача отнюдь не сложная, а я бы сказал, нудная. Сводится к перебору некоторого количества случаев (например, 28 случаев занумерованных парами (x,y), где x - количество белых шашек, y - количество черных шашек, x+y<=6).
> В каждом случае задача аналогична той, что Вы уже решили.

x+y =(!) 6 . Равно строго. Шашек должно быть именно шесть. Потому, что для меньшего количества базы совсем мелкие и идут отдельно.

Делал я так. Сначала сделал нахождение номера позиции без учёта цветности и дамочности ( шашка или дамка ). Таких вариантов : 906192 . А учесть цветность и дамочность - дело техники. Перебираю все их возможные сочетания (4096) и домнажаю на 906192.

Для быстрого нахождения номера позиции из этих 906192, создал двухмерный массив С :
procedure CreatTableMen32and6;
const
BoardSize = 32;
Men = 6;
var
i, j : Integer;
begin
C[0,0] := 1;
for i := 1 to Men do begin
C[0,i] := 0;
end;
for j := 1 to BoardSize do begin
C[j,0] := 1;
for i := 1 to Men do begin
C[j,i] := C[(j-1),(i-1)] + C[(j-1),i];
end;
end;
end;

Это на Дельфи. По массиву быстро нахожу номер нужной позиции так :

function Array2Num32and6(var ArrayOf6Men: array of Integer): Integer;
const
Men = 6;
BoardSize = 32;
var
i, j : Integer;
begin
Result := 0;
i := Men;
for j := Men-1 downto 0 do begin
Result := Result + C[ArrayOf6Men[j], i];
i := i -1;
end;
end;

ArrayOf6Men - это массив 1..6 в который мы запихиваем номера полей (0 - 31) на которых должны стоять шашки. А результат - номер позиции в базе. Правда простой и быстрый алгоритм ?

Теперь же упростить задачу путём начального игнорирования цветности и дамочности неполучится, так как белые шашки не могут стоять на полях 0-3, а чёрные на полях 28-31. Дамки же могут стоять где угодно.
Вот я и думаю, какая же должна быть таблица ? Четырёхмерная что ли ? Путём добавления ещё по измерению на дамочность и цветность. Или какая ? И главное как её сделать. Я не математик потому, для меня это сложно ...


> > Я сам был по уши счастлив, когда написал свой алгоритм.

> Число всех позиций (и возможных и невозможных) C(32,6)*4^6 = 3711762432
> Алгоритм прямо следует из этой формулы: сначала нумераются все сочетания из 32 по 6, а затем всевозможные расстановки номиналов: белая/черная шашка/дамка.

3711762432 - это количество позиций включая невозможные ( те в которых шашки могут стоять и на дамочных полях). А как вычислить только возможные ?

> > По поводу хэша - умножте 2,5 миллиарда на 4 байта ( размер нумерации ) и вы узнаете сколько это будет занимать на диске. Это куда больше чем те лишние 1,2 миллиарда, которые есть сейчас.

> Так Вы же ничего не сказали о размере записи для конкретной позиции. Скажем, если она 100 байт, то способ с хеш-таблицей будет очень даже экономным.
Размерность - бит. =0 - проигрыш, =1 - можно играть дальше.


Ой. Ошибся в предыдущем постинге ArrayOf6Men - это 0..5 , конечно.


> > Эта задача отнюдь не сложная, а я бы сказал, нудная. Сводится к перебору некоторого количества случаев (например, 28 случаев занумерованных парами (x,y), где x - количество белых шашек, y - количество черных шашек, x+y<=6).
> > В каждом случае задача аналогична той, что Вы уже решили.

> x+y =(!) 6 . Равно строго. Шашек должно быть именно шесть. Потому, что для меньшего количества базы совсем мелкие и идут отдельно.

А как же дамки? "Шашкой" я называю именно шашку, но не дамку. Поэтому x+y<=6, остальные 6-x-y это дамки.

Но теперь мне кажется, что проще будет перебрать варианты по-другому.
Пусть i - количество черных шашек/дамок и белых дамок на полях 28..31,
j - количество белых шашек/дамок и черых дамок на полях 0..3.
Они должны удовлетворять следующим неравенствам:
0<=i<=4
0<=j<=4
i+j<=6

Всего 22 различных пары (i,j).

[...]

> > Число всех позиций (и возможных и невозможных) C(32,6)*4^6 = 3711762432
> > Алгоритм прямо следует из этой формулы: сначала нумераются все сочетания из 32 по 6, а затем всевозможные расстановки номиналов: белая/черная шашка/дамка.

> 3711762432 - это количество позиций включая невозможные ( те в которых шашки могут стоять и на дамочных полях). А как вычислить только возможные ?

Количество возможных позиций:

Sum C(4,i)*3^i * C(4,j)*3^j * C(24,6-i-j)*4^(6-i-j) =
= 2503611964

Здесь суммирование ведется по всем i,j как указано выше.
Алгоритм нумерации легко вывести из этой формулы.


> Есть такая задачка, школьная. По дну реки проложен кабель, а в нем 128 проводов. Все провода одного цвета. У монтера есть лодка и простейший тестер - отвертка с лампочкой, показывает наличие напряжения(фазы). К одному берегу подходит линия электропередач. Т.е. имеется источник напряжения. Вот. Задача состоит в том что надо "прозвонить" кабель", т.е. определить концы всех проводов. Сколько раз придется монтеру переплыть реку? Какое наименьшее количество таких ходок вы можете предложить?

Достаточно переплыть два раза. Причем это не зависит от количества проводов.

Сначала монтер разбивает провода по парам и соединяет концы проводов в каждой паре за исключением одной - скажем,
(x[1],y[1]), ..., (x[63],y[63])
и x[0],y[0] - несоединенная пара.

Плывет на другой берег и определяет все пары соединенных проводов там, а так же оставшуюся не соединенную пару.

Плывет назад и соединяет провода так:
(y[0],x[1]), (y[1],x[2]), ..., (y[62],x[63])

Возвращается, находит тот провод и ранее несоединенных (т.е. x[0] и y[0]), который соединен с каким-то другим - это будет y[0], тот "другой" провод, которым он соединен - это x[1]; оставшийся провод из пары (x[1],y[1]) (пара определена на предыдущей ходке) - это y[1], который соединен с x[2] и т.д.
Монтер восстанавливает всю цепочку.
Несоединенные провода также опознаются без проблем.


> > > Эта задача отнюдь не сложная, а я бы сказал, нудная. Сводится к перебору некоторого количества случаев (например, 28 случаев занумерованных парами (x,y), где x - количество белых шашек, y - количество черных шашек, x+y<=6).
> > > В каждом случае задача аналогична той, что Вы уже решили.

> > x+y =(!) 6 . Равно строго. Шашек должно быть именно шесть. Потому, что для меньшего количества базы совсем мелкие и идут отдельно.

> А как же дамки? "Шашкой" я называю именно шашку, но не дамку. Поэтому x+y<=6, остальные 6-x-y это дамки.

А, понял. Можно ещё, называть шашки и дамки - обобщающим словом фишки. Шашки - это простые (не дамки). Дамки - это шашки дошедшие до дамочного поля.


> Но теперь мне кажется, что проще будет перебрать варианты по-другому.
> Пусть i - количество черных шашек/дамок и белых дамок на полях 28..31,
> j - количество белых шашек/дамок и черых дамок на полях 0..3.
> Они должны удовлетворять следующим неравенствам:
> 0<=i<=4
> 0<=j<=4
> i+j<=6

> Всего 22 различных пары (i,j).

> [...]

var
i, j, k : Integer;
begin
k := 1;
for i := 0 to 4 do
for j := 0 to 4 do
if i+j <= 6 then begin
RichEdit1.Lines.Add('№' +IntToStr(k) +' i=' +IntToStr(i) +' j=' +IntToStr(j));
Inc(k);
end;
end;
Да, 22 сочетания. Правда не совсем понимаю что это даёт. И они, могут стоять на разных клетках.


> > > Число всех позиций (и возможных и невозможных) C(32,6)*4^6 = 3711762432
> > > Алгоритм прямо следует из этой формулы: сначала нумераются все сочетания из 32 по 6, а затем всевозможные расстановки номиналов: белая/черная шашка/дамка.

> > 3711762432 - это количество позиций включая невозможные ( те в которых шашки могут стоять и на дамочных полях). А как вычислить только возможные ?

> Количество возможных позиций:

> Sum C(4,i)*3^i * C(4,j)*3^j * C(24,6-i-j)*4^(6-i-j) =
> = 2503611964

> Здесь суммирование ведется по всем i,j как указано выше.
> Алгоритм нумерации легко вывести из этой формулы.

Нет. Далеко не всем легко ! Тут же мы уже не только 6 клеток передаём в функцию, но и что на них стоит. Белые, чёрные, дамки, простые. Их же тоже надо трасформировать туда и обратно.


> > Пусть i - количество черных шашек/дамок и белых дамок на полях 28..31,
> > j - количество белых шашек/дамок и черых дамок на полях 0..3.
> > Они должны удовлетворять следующим неравенствам:
> > 0<=i<=4
> > 0<=j<=4
> > i+j<=6

> > Всего 22 различных пары (i,j).

Или еще проще пусть k=i+j, тогда 0<=k<=6 и количество возможных позиций равно
Sum[k=0..6] C(8,k)*3^k * C(24,6-k)*4^(6-k) = 2503611964

На полях 0..3, 28..31 будем рассматривать всего три номинала: белая дамка, черная дамка и шашка. При этом цвет шашки однозначно определяется ее положением.

Пусть A[p,m,n] - алгоритм нумерующий позиции на поле из p полей, m фишек и n номиналов. Вы уже реализовали алгоритм A[32,6,4], который легко обобщить до произвольных p,m,n.
Заметим, что номер выдаваемый A[p,m,n] лежит в пределах 0..(C(p,m)*n^m)-1

Пусть

T(k) = C(8,k)*3^k
N(k) = C(8,k)*3^k * C(24,6-k)*4^(6-k), где 0<=k<=6;
M(s) = Sum[k=0..s-1] N(k), где 0<=s<=7

Все эти функции можно предварительно вычислить и задать таблично.

Теперь алгоритм нумерации данной позиции:

1. Полагаем k = количество фишек на полях 0..3, 28..31,
нумеруем эти фишки алгоритмом A[8,k,3], обозначим номер u (изменяется в пределах 0..T(k)-1)
2. Нумеруем оставшиеся 6-k фишек на полях 4..27 алгоритмом A[24,6-k,4], обозначим номер v
3. В качестве результата выдаем номер: w = M(k) + T(k)*v + u

Обратный алгоритм определение позиции по номеру w:

1. Находим такое k, что M(k) <= w < M(k+1)
2. Восстанавливаем позицию на полях 0..3, 28..31 алгоритмом обратным к A[8,k,3] по номеру (w-M(k)) mod T(k)
3. Восстанавливаем позицию на полях 4..27 алгоритмом обратным к A[24,6-k,4] по номеру int((w-M(k))/T(k))


Я так понял, что у монтера не тестер, а отвертка показывающая есть напряжение или нет, т.е. на один конец провода должно быть подано напряжение.



> Достаточно переплыть два раза. Причем это не зависит от количества проводов.

> Сначала монтер разбивает провода по парам и соединяет концы проводов в каждой паре за исключением одной - скажем,
> (x[1],y[1]), ..., (x[63],y[63])
> и x[0],y[0] - несоединенная пара.

> Плывет на другой берег и определяет все пары соединенных проводов там, а так же оставшуюся не соединенную пару.

> Плывет назад и соединяет провода так:
> (y[0],x[1]), (y[1],x[2]), ..., (y[62],x[63])

> Возвращается, находит тот провод и ранее несоединенных (т.е. x[0] и y[0]), который соединен с каким-то другим - это будет y[0], тот "другой" провод, которым он соединен - это x[1]; оставшийся провод из пары (x[1],y[1]) (пара определена на предыдущей ходке) - это y[1], который соединен с x[2] и т.д.
> Монтер восстанавливает всю цепочку.
> Несоединенные провода также опознаются без проблем.

Получается что он 3 раза переплыл реку. Это потому что не импользовал источник напряжения. Если использовать - достаточно 2 раза.


Большое спасибо !
Я долго не отвечал, хотел сделать всё это сам и сделал. Почти примерно как вы описываете, только таблицы сделал не для C(8,k)*3^k , а только для степеней 3 и 4 от 0 до 6. Но это в общем не так принципиально. Главное, что я теперь понял как эту задачу и ей подобные решать. Ошибка моя была в том, что пытался свалить дамочные поля и обычные в кучу, а надо было разделить и считать отдельно.

В базе позиций, тех позиций в которых начинающий выигрыает процентов на двадцать больше, чем тех, в которых начинающий проигрывает. Отсюда можно сделать вывод, что с точки зрения теории вероятности у того кто ходит есть преимущество.

Вот интересно, можно ли математическими методами, имея полную базу всех позиций, вывести формулу преимущества ? Или хотя бы попытаться ?


> Поставлена задача - разработать автоматически маршрут передвижения торгового представителя по торговым точкам с учетом времени работы торговой точки. У кого есть какие-то алгоритмы решения этой задачи или что-нибуть по этой теме, помогите, пожалуйста.

Есть мнение, что в готовом виде алгоритм никто не выложит, но если это ещё актуально - могу подбросить идею.

Попробуй сопоставить время перемещения между точками с временем их работы. Так ты можешь получить несколько матриц, которые путём наложения помогут сузить количество вариантов для перебора.

Удачи


Попробуй "жадный алгоритм". Ну, это когда ищется ближайший город, расстояние до него запоминается, затем ищутся расстояния до других городов (Сравнивается расстояние от исходного до конечного напрямую и через найденный). Из получившихся расстояний выбирается наименьшее, и все повторяется сначала. В итоге получишь цепь городов...


> Попробуй "жадный алгоритм". Ну, это когда ищется ближайший город, расстояние до него запоминается, затем ищутся расстояния до других городов (Сравнивается расстояние от исходного до конечного напрямую и через найденный). Из получившихся расстояний выбирается наименьшее, и все повторяется сначала. В итоге получишь цепь городов...

Если зависимости от времени не существует то нет ничего проще.
На карту наносятся все города которые должны посетиться.
Если мы находимся в центре карты то двигаемся по спирали скажем по часовой стрелке к окраине карты не забывая не одного из городов.
В том случае если мы находимся на краю карты то движение происходит также по спирали во внутрь карты,ни один город не забывается.

Если же надо учитывать вместо городов магазины и время их открытия, то на карте наносятся сначала магазины которые открываются самыми первыми и закрываются также самыми первыми- им придаётся самый высокий приоритет, а магазинам закрывающимся последними самый низкий приоритет.
Ведь цель комивояжера за один день посетить ВСЕ магазины.
Принцип тот же но некоторые магазины с низким приоритетом сразу не посещаются.
В принципе надо рисовать в каждую следующию минуту актуализированную карту - во времена компьютера без проблем.
Алгоритм - двигайся по спирали посещая все открытые магазины с учётом приоритета(магазины которые закроются более поздно можно посетить и на обратном пути).
Достигнув или центра города или его окраины возвращаемся по спирали к нашему старту посещая теперь магазины которые уже открылись.
Д.


Меня интересует все, что касается теории чисел. Проблема четырех красок тесно переплетается с задачей о четырех кубах. Известно, что пифагоровы тройки ищутся по схеме: 1) задаются целые положительные взаимно простые числа p и q , причем p < q . Решение: x = q^2-p^2; y = 2pq ; z = q^2+p^2. Совершенно очевидно, что алгебраическое уравнение x^2 + y^2 = z^2 строго выполняется.
А можно ли найти подобное уравнение для x^3 + y^3 + z^3 = v^3 ? Я больше года бъюсь над этой задачей. Удалось найти лишь частные формулы, покрывающие ровно половину всех решений. Но общей формулы найти не посчастливилось.


Пока ниже Аня и другие пытаются обсудить ряд проблем с решением диф.ур. 10 порядка как задачи Коши, и при этом постоянно звучит тема переборов, как грустного явления, то позвою себе осветить тему в той области, где решения еще можно видеть без особых математических усилий и то совершенно очевиден вывод -
ОСТАВЬ НАДЕЖДУ ВСЯК СЮДА ВХОДЯЩИЙ!
Речь пойдет о уравнениях 2 порядка, хорошо известных уравнений движения Ньютона для материальной точки.
Если у нас тело вылетает из одной точки, а сил действующих на нее нет, то пути-дорожки тела примитивны и однообразны как на рис. 1 изображенном ниже


Конечно путей маленько побольше, чем я нарисовал, но идея понятна?
Поставим на пути тела некий шпынек маленьких размеров - и картина невероятно изменится


Добавим еще один шпынек и картина станет просто ужасающей


Но мы не успокоимся и добавим еще -цать шпыньков - и нарисовать уже более ничего нельзя будет.
Что здесь можно найти перебором? Да ничего. Любой суперкомпьютер можно посадить на подобных задачках добавлением к нарисованным шпынькам еще пару сотен шпыньков.
Задачка не вымышлена. В ионосфере для распространения радиоволн она сильно нужна. Ионосфера - это мятая и рваная фольга, это возможно покруче шпыньков.
Разумеется я могу решать эту задачу, но речь сейчас идет не об этом а о необычном мышлении математиков, не желающих признать факт принципиальной невозможности переборов.
Именно мышление математиков, их особенный ход мысли вызывают глубокое внимание.
15 августа 2004 г. 16:28:


Я давно занимаюсь топологией, и в частности, проблемой четырёх и пяти красок. Знаю только, что учебники восьмидесятых годов и более ранние говорят, что решения для четырёх красок не найдено до сих пор. Сществует доказательство, что пяти красок достаточно, и есть предположение, что достаточно и четырёх. Если Вам кажется, что Вы нашли решение, пишите мне на e-mail Le_Bomb-II@bk.ru
Я готов проверить ход Ваших мыслей, так как имею некоторый опыт подобной деятельности.
С уважением, Tinky


> Я давно занимаюсь топологией, и в частности, проблемой четырёх и пяти красок. Знаю только, что учебники восьмидесятых годов и более ранние говорят, что решения для четырёх красок не найдено до сих пор. Сществует доказательство, что пяти красок достаточно, и есть предположение, что достаточно и четырёх. Если Вам кажется, что Вы нашли решение, пишите мне на e-mail Le_Bomb-II@bk.ru
> Я готов проверить ход Ваших мыслей, так как имею некоторый опыт подобной деятельности.
> С уважением, Tinky

Теорема о раскраске карты на плоскости в четыре цвета была доказана К. Аппелем и В. Хакеном в 1976 г с помощью ЭВМ (K. Appel and W. Haken, Every planar map is four colorable. Part I. Discharging. Illinois J. Math. 21 (1977), 429-490., Part II. Reducibility. Illinois J. Math. 21 (1977), 491-567. см. также http://www.math.gatech.edu/~thomas/FC/fourcolor.html и http://mathworld.wolfram.com/Four-ColorTheorem.html). Сейчас речь может идти о нахождении более простого, более короткого и (желательно!) без привлечения компьютеров доказательства этой теоремы традиционными средствами. Такие попытки периодически предпринимаются (запустите поисковик с подходящими ключевыми словами - наверняка что-нибудь выловите). Одна из таких попыток - работа Х-Ander'a (см. 10963). По-моему - удачная. Сейчас готовится к публикации. Вашу просьбу ему переадресую (если он раньше с Вами не свяжется).


Кому интересно - за развитием событий можно следить здесь:

http://www.alexplus.ru/x-ander/4colours/


Помогите пожалуйста с решением следующей задачи:
Имеется треугольник из чисел.
7
3 8
8 1 0
2 7 4 4

Вычислить наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке треугольника и заканчивающемся на основании треугольника.
Каждый шаг может осуществляться вниз по диагонали вправо или вниз по диагонали влево.
Количество горизонталей тр-ка 1..1000
13 марта 2005 г. 15:44:



Типичная учебная задача на динамическое программирование. Начиная снизу, подсчитываем "качество" вершин. В самом низу=весу, далее - как максимум веса нижних соседей+вес.


Всем привет!
на днях дали тему диплома "разработка модели транспортной задачи как комбинаторной и методы её решения"
Сразу говорю, что под этим скрываеться!
1. транспортная задача
2. 3 целевых функции
3. ограничения
4. ограничения многогранника

вообщем я попал! графы, комбинаторика - что делать я не знаю! ни литературы ничего вообще нету! немного в инете нарыл, но но но!
Люди кто может сталкивался с этим, - помогите пожалуйста! если что пишите на sirius128@rambler.ru ICQ 316712091 ЗАрание ВАМ благодарен!
06 апреля 2006 г. 18:23:



Подскажите, где и как искать решение задачи...

Есть детали и палки, которые надо порезать на эти детали. И палки и детали разного размера.
Резать надо так, чтобы суммарный отход (длинна обрезков нарезанных палок) был минимальным.
Количество деталей порядка 300, палок ~100.
Линейным программированием, похоже не решить за приемлимое время. Кто понимает нюансы таких задач, может любезно подтолкнет на мысль...
Конечно есть еще понятие деловой отход и т.д., но к принципу кроя он мне кажется отношения не имеет.
Я думаю, что такая задача не раз решалась уже и алгоритмы существуют, но не знаю как подступиться...
Спасибо.


> Подскажите, где и как искать решение задачи...

> Есть детали и палки, которые надо порезать на эти детали. И палки и детали разного размера.
> Резать надо так, чтобы суммарный отход (длинна обрезков нарезанных палок) был минимальным.
> Количество деталей порядка 300, палок ~100.
> Линейным программированием, похоже не решить за приемлимое время. Кто понимает нюансы таких задач, может любезно подтолкнет на мысль...
> Конечно есть еще понятие деловой отход и т.д., но к принципу кроя он мне кажется отношения не имеет.
> Я думаю, что такая задача не раз решалась уже и алгоритмы существуют, но не знаю как подступиться...
> Спасибо.

Если я правильно понял, то требуется из 100 палок различной длины нарезать З00 отрезков тоже различной длины. Так как законов распределения длины палок L=f(n)и длины отрезков X=g(n)в задаче не указано, то не о чем и горевать. Каждую палку разрежем на три равные части и получим три комплекта по 100 отрезков разной длины. Если не будем сильно стараться в точности деления на 3, то получим 300 отрезков разной длины, с достаточно большой точностью копирующих первоначальный закон распределения длины палок.


Или я не понял ответ или Вы не восприняли задачу, как я ее хотел объяснить ;)

Количество палок и деталей задано до начала оптимизации. Максимльно палок 100, а деталей 300 (из практики взятые значения чтобы показать трудоемкость задачи). Размеры и палок и деталей тоже заданы и все могут быть разные!

То есть возникает задача какую палку взять и на какие детали ее нарезать, чтобы получить минимальный отход. Затем так же для следующей палки и так далее, пока есть что резать или пока не кончатся детали...

Так вроде понятнее пояснил. Процесс кажется простым, но оптимизировать его я затруднился.


> Или я не понял ответ или Вы не восприняли задачу, как я ее хотел объяснить ;)

> Количество палок и деталей задано до начала оптимизации. Максимльно палок 100, а деталей 300 (из практики взятые значения чтобы показать трудоемкость задачи). Размеры и палок и деталей тоже заданы и все могут быть разные!
> То есть возникает задача какую палку взять и на какие детали ее нарезать, чтобы получить минимальный отход. Затем так же для следующей палки и так далее, пока есть что резать или пока не кончатся детали...
> Так вроде понятнее пояснил. Процесс кажется простым, но оптимизировать его я затруднился.

Задача не из арифметики и математики. Вам нужен алгоритм перебора что-ли? На алгоритмическом языке? Циклы сортировки и перебора Вам знакомы? Не на палках же обяснения нужны. Если задача не касается программирования, то философия ни к чему.


> > Количество палок и деталей задано до начала оптимизации. Максимально палок 100, а деталей 300 (из практики взятые значения чтобы показать трудоемкость задачи). Размеры и палок и деталей тоже заданы и все могут быть разные!

> Задача не из арифметики и математики. Вам нужен алгоритм перебора что-ли? На алгоритмическом языке? Циклы сортировки и перебора Вам знакомы? Не на палках же обяснения нужны. Если задача не касается программирования, то философия ни к чему.
Я бы решал задачу в экселе складывая по отдельности длины деталей(матрица, у которой удалены сложение длин деталей сами с собой).
Сравнивая полученные суммы с длиной палок с помощью функции минимум -максимум искал бы наименьшие и наибольшие отходы полученные при вычитании(ещё одна матрица).Наименьшие отходы должны стремиться к нулю, наибольшие отходы быть больше самой короткой ещё не изготовленной детали.
Найдя соответствующую пару, удаляем её из сортимента и повторяем процедуру.
Но какой прок от решения этой задачи в экселе, если она не будет реализованна на конкретном сортировочном автомате? Как будут вводиться данные длин палок, как будут выискиваться нужные палки?



> Кому интересно - за развитием событий можно следить здесь:
> http://www.alexplus.ru/x-ander/4colours/
Давно вышла книга Горбатова, в 80-х или 90-х годах. Это - советский ещё специалист по теории графов. Теорема о 4-х красках доказывается в четыре строчки. Перед ней, правда, несколько маленьких лемм. Книга лежит у меня на шкафу наверху, но искать - долго.


Как проверить опорное решение методом потенциалов?


> > Кому интересно - за развитием событий можно следить здесь:
> > http://www.alexplus.ru/x-ander/4colours/
> Давно вышла книга Горбатова, в 80-х или 90-х годах. Это - советский ещё специалист по теории графов. Теорема о 4-х красках доказывается в четыре строчки. Перед ней, правда, несколько маленьких лемм. Книга лежит у меня на шкафу наверху, но искать - долго.

Есть ещё более краткое доказательство, советского ещё специалиста, опубликованное в "Вестнике Пермского университета. сер. Математика. Механика. Информатика. за 2006 г., с. 86-87.


У меня такая вот задача:
Требуется сделать систему планирования для игрушечной железнодорожной станции. Система получает "сверху" заявки-требования на выполнение каких-то ж/д операций (например, принять поезд, отправить поезд) с дополнительными указаниями, среди которых: назначение (на какой путь, на какой перегон), приоритет (низкий, средний, высокий), требуемое время выполнения (например, отправить в 13-30). Каждая заявка-требование (например, принять поезд на 3-й путь) может быть разложена на некоторое число элементарных операций, которые могут быть разнесены во времени (задать маршрут от светофора Н до стрелки 1, затем от светофора НМ1 до 3-го пути) и могут иметь альтернативы (различные маршруты следования из одной точки в другую). Известно, что на станции одновременно могут выполнять несколько операций (поезда могут ездить параллельно по разным трассам маршрутов).
Заявки валятся постоянно, их надо реализовывать, каждый раз перепланируя (так как возможно появление заявки с более высоким приоритетом и надо реализовать её раньше остальных).

Вот я голову ломаю, какими математическими методами можно построить оптимальное расписание выполнения элементарных операций, чтобы по заданным критериям (минимум затраченного времени, минимум пройденного пути) выполнить все заявки (не забыв про приоритет).

Я в математике очень не силён, поэтому представляю это себе так:
-Теория графов (модель станции, как граф) – разложение заявок на элементарные операции;
-Линейное программирование (транспортная задача) - оптимизация трасс маршрутов по критериям путь и время;
-Сетевое планирование – порядок элементарных задач, критерий время;
-Имитационное моделирование – поиск наиболее оптимальной последовательности. Проигрываются различные варианты близких по оптимальности решений для того, чтобы определить, какой из них наиболее удовлетворяет критериям оптимизации. (чего-то хочется имитационное моделирование всобачить, хотя оно, возможно, и лишнее).

Буду рад любому совету по стратегии реализации этой задачи, так как не хочется промахнуться на таком раннем этапе :)


Добрый день!
Помогите решить задачу фигурного кроя! Все знают об алгоритме размещения прямоугольных объектов на плоскости, однако каково может быть решение размещение объектов со сложными кривыми? Сделал алгоритм укрупнения и упращения объектов, однако терубемой точности достичь не удалось!
Возможно кто-то уже сталкивался с такой задачей? Какие есть мысли?


помогите составить математическуя модель, и способ решения данной задачи:
АСУ состоит из N элементов. Число соединений между элементами, определяемое структурой АСУ, задается симметричной матрицей ||C ij|| i,j=1..N. Из условий эксплуатации системы следует, что целесообразно разбить АСУ на m блоков, в каждом из которых не более n элементов. При разбиении системы на блоки одни сзязи окажутся внутриблочными, другие- внешними. Задача: минимизировать число внешних соединений (или максимизировать число внутренних связей).
Спасибо


Дано: складское помещение (высота а, ширина б, длина с). Объемы складируемой тары (х,y.z). Каким оптимальным должно быть размещение товара на складе, чтобы задействовать максимальное количество площади склада, при ограниченном объеме склада и площадью свободна хода для работников склада и техники?


> Интересует ли кого-нибудь из обитающих здесь заявленный сабж? Если да, то у меня есть нечто, напоминающее простое и понятное доказательство этой теоремы. Нужен трезвый взгляд и умная критика.
> 10 марта 2004 г. 19:14:

см. стаью автора с краким вариантом доказательства на странице
http://www.uresearch.psu.ru/files/articles/17_89592.doc

в журнале
www.uresearch.psu.ru


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100