Пошевелим извилинами?

← →
NetKnight (2003-12-10 00:03) [0]

Вот один знакомый подкинул задачку, очень кстати помогает человеку научиться думать гибко, я голову поломал изрядно!
Условия:
Написать на любом языке (можно даже блок-схемами) алгоритм, который находит кратчайший путь из либиринта размерами n*n.
Входные параметры:
Координаты начального и конечного пункта и карта лабиринта.
Программа не должна при выполнении повиснуть и должна работать быстро, перебор всех вариантов по очереди сведёт на нет работу, если размер лабиринта хотя бы 100*100 (Это около 100 в 100 степени вариантов)

← →
cyborg (2003-12-10 00:09) [1]

Поиск пути - волновой алгортм
10000 ячеек 9999 проходов в худшем случае :)

← →
cyborg (2003-12-10 00:11) [2]

Если в два направления, то может быть в 2 раза быстрее

← →
easy (2003-12-10 00:12) [3]

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

← →
Rouse_ (2003-12-10 01:37) [4]

Миллионы статей на эту тему в сети...
Советую изучить ссылки на "Поиск пути" в любом поисковике...
Самым лучшим из опыта считаю нейросети... но... (как всегда это НО!!!) требуется их обучение...

← →
Рамиль (2003-12-10 09:22) [5]

Обычное динамическое программирование. Получается что то типа дерева. Идешь по ветке до тупика возвращаешся на шаг назад пробуешь в другом направлении. и т. д.

← →
Danilka (2003-12-10 09:33) [6]

[4] Rouse_ © (10.12.03 01:37)
чему их обучать, если лабиринт каждый раз будет разным?

Согласен с
[1] cyborg © (10.12.03 00:09)
кода будет - строчек десять - двадцать от силы, задачка на пол-часа.

← →
Danilka (2003-12-10 09:39) [7]

[5] Рамиль © (10.12.03 09:22)
Лабиринтом может быть, например, пустое помещение, стартуешь из какого-нибудь угла, а точка назначения - центр помещения. Ну и какое тут дерево? Умучаешься тупики искать :))

← →
Danilka (2003-12-10 09:43) [8]

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

← →
Gero (2003-12-10 09:49) [9]

>Рамиль © (10.12.03 09:22) [5]
Ты не прав. Это не будет лучшим решением. К примеру ветка, по которой ты пошел, изгибается раз десять, а потом приводит к выходу. А другая ветка, по которой ты, естетвенно не пошел, ведет прямо к финалу. И какой же это будет кратчайший путь?

← →
Рамиль (2003-12-10 09:59) [10]

Насчет кратчайшего просмотрел, каюсь;)

← →
NetKnight (2003-12-10 16:03) [11]

Ни одной даже приблизительно правильной версии.. :)
Волновой алгоритм - это как? Если ты имеешь введу рекурсивный метод, где просматриваются все варианты - это очень медленный вариант (Знаешь например сколько времени занимает перебор 6 значного пароля? Это 255^6 вариантов. А это побольше получится, чем перебор паролей)

← →
Danilka (2003-12-10 16:13) [12]

[11] NetKnight © (10.12.03 16:03)
Набери в поисковике "волновой алгоритм" и узнаешь, как это :))
А на счет скорости, ты путаешь, на самом деле там все быстро. :))

Вообще-то, про него еще в институте рассказывали, курсе на 2-3м..

← →
Danilka (2003-12-10 16:22) [13]

Вообще, еще в древности на 8086 процессоре, PCAD делал разводку печатных плат по волновому алгоритму, и не жаловался ни на какие корни, хотя размеры там были поболее чем 100х100 и элементов - куча великая. :))

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

← →
VictorT (2003-12-10 17:19) [14]

А в чём подвох? Завтра подкину свою демку на пару десятков строк с кучей коментариев (из дома тока возьму). Когда-то писал специально для Blackweber-а (обитал тут такой), именно с целью продемонстрировать алгоритм. А ещё раньше на спектруме делал игрушку типа пакмана, там тоже использовал волновой алгоритм.

← →
Cosinus (2003-12-10 17:39) [15]

http://www.codenet.ru/progr/alg/way.php

← →
VictorT (2003-12-11 11:34) [16]

Вот исходник моей реализации. ЕХЕ выложить не смог, т.к. испортился файл на дискете :( А откомпилить тут нечем счас :(

// Програмка, демонстрирующая поиск кратчайшего пути в лабиринте с // помошью волнового алгоритма. Написана специально для Blackweber-а. // (с) 2002 VictorT // Тестировано на Turbo C++ 3.0 // В файле demowave.map содержится карта лабиринта и начальная и конечная // точки пути. Формат файла следующий: первых два числа - координата // начальной точки пути. Дальше идёт карта лабиринта, причём 255 обозначает // стенку, а 0 - пустое пространство. Конечная точка пути обозначена 1-ей. #include <string.h> #include <stdio.h> #include <conio.h> #include <dos.h> // Массив, содержащий карту лабиринта. unsigned char map[20][12]; // Значение 255 обозначает стенку. char wave(unsigned char n) // Функция, получающая n-ный фронт волны. { // Сканируется массив с картой лабиринта, char flag = 0; // и если обнаруживается елемент со for (int i = 1; i < 11; i++) { // значением, равным n, то левее, for (int j = 1; j < 19; j++) // правее, выше и ниже заносится if (map[j][i] == n) { // значение n+1, если там не if (map[j + 1][i] == 0) { // содержится 255 (т.е. стенка). map[j + 1][i] = n + 1; // Если новый фронт не найден, flag = 1; // возвращается 0. } if (map[j - 1][i] == 0) { map[j - 1][i] = n + 1; flag = 1; } if (map[j][i + 1] == 0) { map[j][i + 1] = n + 1; flag = 1; } if (map[j][i - 1] == 0) { map[j][i - 1] = n + 1; flag = 1; } } } return flag; } char step(int &x, int &y) //Функция, по текущим кординатам дающая координаты { // для следующого шага, оптимальные для приближения к // конечной точке. Возвращает 0, если дошли до конечной // точки. if (map[x][y] == 2) // Если достигли конечной точки, return 0; // то возвращаем 0. if (map[x + 1][y] < map[x][y]) { // x++; // Выбираем return 1; // такое } // направление, if (map[x - 1][y] < map[x][y]) { // при котором x--; // уменьшается return 1; // значение } // елемента if (map[x][y + 1] < map[x][y]) { // массива y++; // для следуюшей return 1; // координаты } // по сравнению y--; // с предидущей. return 1; // } void main() { // Открываем для FILE *in_file; // чтения файл if ((in_file = fopen("demowave.map", "r")) != NULL) { // demowave.dat int x, y; // Читаем из файла координаты fscanf(in_file, "%d%d", &x, &y); // начальной точки unsigned int temp; // for (int i = 0; i < 12; i++) { // Читаем for (int j = 0; j < 20; j++) { // из файла fscanf(in_file, "%d", &temp); // в массив map[j][i] = temp; // карту } // лабиринта. } // fclose(in_file); unsigned char n=1; while(wave(n)) // Пускаем волну из конечной точки n++; // до заполнения всего лабиринта. clrscr(); for (i = 0; i < 12; i++) { // for (int j = 0; j < 20; j++) { // Выводим if (map[j][i] == 255) // лабиринт textbackground(4); // показывая if (map[j][i] == 1) // при этом textcolor(10); // для cprintf("%03u", map[j][i]); // наглядности textbackground(0); // алгоритма textcolor(7); // поиска if (j != 19) // значение cprintf(" "); // каждого } // елемента cprintf("\r\n\n"); // массива. } // textcolor(14); // Отмечаем жёлтым gotoxy(x * 4 + 1, y * 2 + 1); // цветом начальную cprintf("%03u", map[x][y]); // точку пути. while(step(x, y)) { // С помощью функции step() получаем gotoxy(x * 4 + 1, y * 2 + 1); // координаты каждой следующей точки cprintf("%03u", map[x][y]); // пути и так-же отмечаем жёлтым delay(500); // цветом. } } else { puts("Файл demowave.map не найден \n"); } delay(1000); }

Пример файла demowave.map

18 7 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 000 255 000 000 255 000 000 255 000 000 000 000 000 000 000 000 000 000 255 255 000 000 000 000 255 000 000 000 000 255 000 000 000 000 000 000 000 000 255 255 000 255 000 255 255 000 255 000 000 255 000 000 000 000 000 000 000 000 255 255 000 255 000 000 000 000 255 000 000 255 000 000 000 255 255 255 255 000 255 255 000 255 255 255 255 255 255 000 000 255 000 255 255 255 000 000 000 000 255 255 001 000 000 255 000 000 000 000 000 255 000 000 000 255 255 000 255 255 255 255 255 255 000 255 000 255 000 000 000 255 000 000 000 255 000 000 000 000 255 255 000 000 000 255 000 255 000 000 000 000 000 255 000 255 000 000 000 000 255 255 000 255 255 255 000 255 000 000 000 000 000 255 000 000 000 000 000 000 255 255 000 000 000 000 000 255 000 000 000 000 000 255 000 000 000 000 000 000 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255 255

← →
VictorT (2003-12-11 13:26) [17]

Cкачал компилятор, откомпилил. Тут всё готовенькое лежит (исходник, карта, ехе-шник), 14 Кб:
http://kalina.webm.ru/temp/demowave.rar

← →
SergP (2003-12-11 14:58) [18]

> VictorT © (11.12.03 11:34) [16]

Я когда-то давно писал на assm Z80 прогу для Spectrum (может помнишь такое) для трассировки печатных плат, где использовал волновой алгоритм. Сначала делал по тому принципу что и твоя прогу. т.е. постоянно сканировал всю "map" в поисках очередного номера фронта волны, чтобы распространять волну дальше (вверх, вниз, вправо, влево и на другой слой). прога работала, но так как это был 8 разрядный процессор с тактовой частотой 3,5 Мгц, скорость работы мне не нравилась. А потом мне в голову стукнула мысль не сканировать постоянно всю карту, а запоминать координаты в памяти. Правда я сделал запоминание координат через стек, типа если в данную координату можно распространять волну, то записывал туда номер фронта волны, и сохранял координаты в стеке ( push hl ). У меня было выделенно в памяти 2 участка для запоминания координат. На четных шагах из одного брались координаты записаные на предыдущем шаге, и вычисленные новые координаты сохранялись в другой участок при помощи стека, а при нечетных шагах наоборот (т.е. эти оба участка какбы менялись местами).

Я замерял время необходимое проге для трассировки тестового примера (плата на которой было 6 штук 16-выводных микросхем) при первом варианте и после описаной модификации волнового алгоритма. Как оказалось второй вариант работал быстрее в 50 раз!!! И это при том что в первом варианте я уже оптимизировал все что мог с целью добиться большего быстродействия. Т.е. могу с уверенностью сказать что более оптимизировать там было некуда...

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

← →
VictorT (2003-12-11 16:30) [19]

> SergP © (11.12.03 14:58) [18]

А я на том же Спектруме пакмана писал используя этот алгоритм.
А для трассировки плат на Спектруме видел одну прогу, не помню, как называлась, немецкая, там ещё на заставке этот, как его, из мультфильма, с паяльником и микросхемой...

← →
VictorT (2003-12-11 16:31) [20]

тока там кажись не волновой алгоритм использовался, а лучевой...

← →
VictorT (2003-12-11 18:44) [21]

да уж... заглючило... крот там был :)

← →
NetKnight (2003-12-11 18:47) [22]

Я сделал с использованием волнового алгоритма, но с использованием 2-х волн, выходящих из начала и конца.
Была лишь одна проблема - выяснить, когда встретились волны, т.к. волна могла встретиться сама с собой. :)
Вообщем кому надо могу выложить прогу, она делает прорисовку на Вин Апи и показывает с нумрацией волны и конечноый кратчайший путь. В проге используется только один масив до тех пор пока волна не столкнётся с другой, только тогда для проверки задействуется второй массив равный первому.

Серг, было бы интересно взглянуть на это, как ты эти масивы обрабатывал? :)

← →
NetKnight (2003-12-11 18:54) [23]

Кстати, возник тут же вопрос, как наилучшим образом скопировать динамический двухмерный массив?
var M1 : array of array of integer; M2 : array of array of integer; begin M1 := M2; // Тут передача указателя, а не копирование. Выдаёт ошибку. M1 := copy (M2,0,length(M2)); // Выдаёт ошипку соответствия типов, как и в прошлом примере. SetLength(M1,length(M2)); for i:=0 to length(M2)-1 do M1[i] := copy(M2[i],0,length(M2)-1); // Та же ошибка end;

Работает только вариант тупого перебирания по обоим индексам и подстановке значений (Это n*n итераций!)

По сему вопрос, как быть?!

Пошевелим извилинами? Найти похожие ветки