Форум на Исходниках.RU

Нахождение кратч. пути межд. точками

RADIX — Mon, 23 Sep 2002 16:42:48 +0000

RADIX: Делим задачу на две -
1 доступность
2 кратчайший путь
доступность по волновому методу рекурсивным обходом соседних вершин.
если так же считать путь, то можно и зашкалить стек, потому считаем перебором ячеек до тех пор пока не перестанет менятся информация о кратчайших путях

Нахождение кратч. пути межд. точками

RADIX — Mon, 23 Sep 2002 16:37:53 +0000

RADIX: Блин, достал PuntoSwitcher, как хочет, так и переключает
отправил на адрес belyaev.iv@mail.com, а другой не не доступен.
Если нужен exe, то сообщи здесь.

Нахождение кратч. пути межд. точками

RADIX — Mon, 23 Sep 2002 16:28:07 +0000

RADIX: YtНедавно ограммил халяву одному студенту - 25х25
Расчет практически не заметен под TVision
Dscska. на мыло b.ivan@nursat.kz

Нахождение кратч. пути межд. точками

Машина — Sat, 21 Sep 2002 21:24:57 +0000

Машина:

Цитата rhf, 13.09.02, 20:45:58

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

Да не переделывать, а это и есть ненаправленный граф :), причём упрощеный.

Нахождение кратч. пути межд. точками

Иван — Wed, 18 Sep 2002 13:28:31 +0000

Иван: К rhf. Видимо Вы кинули пример на глючное мыло, ну или чтото с ним случилось по дороге. Прошу кинуть ещё раз на b.ivan@nursat.kz

Нахождение кратч. пути межд. точками

tserega — Tue, 17 Sep 2002 13:47:15 +0000

tserega: Так я и не говорю, что быстрый. Вопрос был хоть какой-то алгоритм. Мое дело - предложить, другое дело оптимизация. :D

Нахождение кратч. пути межд. точками

rhf — Mon, 16 Sep 2002 22:30:39 +0000

rhf: 2 tserega, хе......уж точно не быстрый :) четыре вложенных цикла......
2 Иван, зная название алгоритма не проблема найти его в сети....
зыж примерчик решения на мыло вам скинул, проверьте.

Нахождение кратч. пути межд. точками

tserega — Mon, 16 Sep 2002 17:54:55 +0000

tserega:

Цитата Иван, 16.09.02, 17:57:33

в нашей деревне таких терменов просто не знают

Аналогия волновой алгоритма - ты бросаешь камень в воду и смотришь, как расходятся волны от него. (Конечно, так можно и "поехать", но не в этом дело!). На N-ом ходу ты ставишь во все соседние клетки с числом (N-1) min(N, число в клетке).
Пример на паскалях-псевдокоде:
Mas[X,Y] = -1 - стена
Mas[StartX, StartY]:=1;
for i:=1 to N do
for j:=1 to N do
for k:=1 to N do
for l:=1 to N do
if Mas[I,J] <> -1 Then
Mas[I,J]:=минимум из значений в соседних клетках + 1;

Я не гарантирую, что алгоритм самый быстрый, но что работает - точно...

Нахождение кратч. пути межд. точками

Иван — Mon, 16 Sep 2002 13:57:33 +0000

Иван: Глубокоуважаемый и высокообразованый rhf, в нашей деревне таких терменов просто не знают. А насчет лабиринтов, но ответ отрицательный: просто пара линий. Буду примного благодарен за любую доку, пример на любой (кроме ассемблера) язык, или просто письмо с оъяснением. Мыло моё (личное) :

b.ivan@nursat.kz

или belyaev.iv@mail.com, но с этим чо-то не так, видимо с кодировкой.

Нахождение кратч. пути межд. точками

rhf — Sat, 14 Sep 2002 15:49:48 +0000

rhf: ну как сказать......... не самый медленный.
нужно будет матрицу вашу правда малость преобразовать для этих нужд.

ЗЫ а вообще у вас тут что-то вроде лабиринта..... можно волновым алгоримом пользоваться

Нахождение кратч. пути межд. точками

Иван — Sat, 14 Sep 2002 13:26:25 +0000

Иван: А енти ваши Дейкстры быстрые?

Нахождение кратч. пути межд. точками

rhf — Fri, 13 Sep 2002 16:45:58 +0000

rhf: да тут способов море....
можно для этих нужд любой алгоритм поиска переделать, например Дейкстры...

Нахождение кратч. пути межд. точками

Иван — Fri, 13 Sep 2002 15:34:50 +0000

Иван: Ладно, надеюсь Вы не обидились за "Ненадо алгоритмов", они всегда нужны, только тут проблема: все хорошие проги писаны на С++, а я в нем господин дерево, если сможите объяснить языком VB, или Delphi, буду примного благодарен.

Я тут сам попробовал написать так: нашёл окольный путь, и прописал его в другом масссиве, сколько ходов потребовалось для прохождения до данной точки массива. Потом ещё раз прошёлся, но если получалось, что путь длиннее, его обрывало. И так до бесконечности, пока не поймёт, что путь найден. Подобный способ есть в одной книжке по делфи, но там он 5x5, и какой то принцип свой, вроде массив 2д, а координаты опеределявтся одним аргументом. Ну в общем, в массиве 100x100 на всё это уходит около 2 минут, в реал тайм не катит.

Нахождение кратч. пути межд. точками

Sanya — Fri, 13 Sep 2002 12:37:14 +0000

Sanya: Если по диагонали нельзя ходить, то задача разбиваеться на поиск кратчайшего растояния в обычных масивах - рядках и столбиках етой матрицы

Нахождение кратч. пути межд. точками

Demo_S — Thu, 12 Sep 2002 20:31:00 +0000

Demo_S: алгоритмов не надо, алгоритмов не надо... а как же тогда?:)
ладно, попробуем:):)

попробуй сделать второй массив, и начинай расширятся из одной из этих точек..
во все сосдение, которые нули ставь 1, во все, в которые можно добраться из соседних (клетки, соседние с соседними и равные 0) ставь 2
те, куда дойдешь за три хода, в них ставь 3.
так доползешь и до своей:) второй точки. что в нее напишешшь, то и будет кратчайшее расстояние.. а путь потом можно восстановить:)

Нахождение кратч. пути межд. точками

Иван — Thu, 12 Sep 2002 14:04:37 +0000

Иван: Как найти кратчайшее расстояние между двумя точками в 2D массиве? Причем ийти только через ичейки хранящие ноль. Алгоримов не надо, а советы давайте.