компьютерный форум
Вернуться   Компьютерный форум > Программирование и вебстроительство > Программирование

Ответ
 
LinkBack Опции темы Опции просмотра
Старый 23.01.2006, 05:10   #1
Gem
Пользователи
 
Регистрация: 23.01.2006
Сообщений: 8
По умолчанию

Необходимо реализовать задачу: есть некий лабиринт, представленный матрицей с несколькими выходами (например):

111111
001100
100001
110111

0 - свободные ячейки, 1 - стены
Пользователь выбирает начало пути, нужно найти выход, кратчайший путь из лабиринта. Планирую реализовать на Delphi. Кое-что в интернете есть на тему лабиринтов, там задаются начальный и конечный пункты, у меня конечный пункт не задается. Вообщем, не могу этот алгоритм подстроить под свою задачу, т.к. не совсем он мне понятен. Пожалуйста помогите, желательно конечно на примере. :help:




Gem вне форума  
Digg this Post!Bookmark Post in Technorati
Ответить с цитированием
23.01.2006, 05:10
Техник
реклама
По умолчанию

Старый 23.01.2006, 22:44   #2
Пользователи
 
Регистрация: 07.12.2004
Сообщений: 783
По умолчанию

Значит так, раз не совсем понятен алгоритм - попробую рассказать:
Допустим, тебе надо попасть сверху-вниз... Если под текущим элементом 0, тогда переходим на следующую строчку, если 1 - проверяем следующий.
вот...
Andy вне форума  
Digg this Post!Bookmark Post in Technorati
Ответить с цитированием
Старый 24.01.2006, 03:27   #3
Gem
Пользователи
 
Регистрация: 23.01.2006
Сообщений: 8
По умолчанию

2 Andy,
это понятно, но вокруг текущего элемента 4 ячейки (верхняя, нижняя, правая и левая), куда можно ходить, а если можно в две ячейки ходить, как у элемента [3,3], нужно просчитать все варианты, да и сразу то неизвестно, у текущего элемента один или несколько вариантов идти дальше - вообщем как программно реализовать не представляю, как все учесть...
:huh:
Gem вне форума  
Digg this Post!Bookmark Post in Technorati
Ответить с цитированием
Старый 24.01.2006, 10:18   #4
Пользователи
 
Регистрация: 03.01.2006
Сообщений: 75
По умолчанию

Есть куча различных процедур поиска минимального пути.
Данная процедура рекурсивная (взята из теории графов)


var na,ko,p,n,i,j,mm,dl:longint;
bil: array [1..100] of boolean;
put: array [1..100] of longint;
a: array [1..100,1..100] of longint;
min,s: string;
t1,t2:text;
procedure po(ng,kg,c:longint);
var ii:longint;
begin
if ng=kg then begin
if dl
seva_avi вне форума  
Digg this Post!Bookmark Post in Technorati
Ответить с цитированием
Старый 25.01.2006, 03:43   #5
Gem
Пользователи
 
Регистрация: 23.01.2006
Сообщений: 8
По умолчанию

2 seva_avi,
спасибо, буду разбираться, будут вопросы - обязательно поинтересуюсь
Gem вне форума  
Digg this Post!Bookmark Post in Technorati
Ответить с цитированием
Старый 27.01.2006, 04:41   #6
Gem
Пользователи
 
Регистрация: 23.01.2006
Сообщений: 8
По умолчанию

2 seva_avi,
вопросы есть:
1. Не могу понять na-это начало пути (заданное пользователем), если да, то почему он задается строкой массива а[], а не конкретной ячейкой, ko - это конец пути, если да, то у меня нет конца пути - их несколько.
2. Не вижу, где используются t1 и t2. Из t1 должен загружаться массив в а[]? Когда выводится путь в t2?
3. Почему в пути, который был проделан, записывается только номер столбца матрицы а (put[c]:=ii?
Если разберусь в этих вопросах, наверняка появятся новые. :help:
Gem вне форума  
Digg this Post!Bookmark Post in Technorati
Ответить с цитированием
Старый 27.01.2006, 07:23   #7
Пользователи
 
Регистрация: 25.01.2006
Сообщений: 2
По умолчанию

Цитата:
Originally posted by Gem@27.01.2006 - 06:41
[b] 2 seva_avi,
вопросы есть:
1. Не могу понять na-это начало пути (заданное пользователем), если да, то почему он задается строкой массива а[], а не конкретной ячейкой, ko - это конец пути, если да, то у меня нет конца пути - их несколько.
2. Не вижу, где используются t1 и t2. Из t1 должен загружаться массив в а[]? Когда выводится путь в t2?
3. Почему в пути, который был проделан, записывается только номер столбца матрицы а (put[c]:=ii?
Если разберусь в этих вопросах, наверняка появятся новые. :help:
Почитай книжечку "Теория алгоритмов" которую Кнут написал, а именно раздел графов и все станет понятным (если конечно книжку поймёшь)...

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

З.Ы. - Откажись от формальной логики
greeka вне форума  
Digg this Post!Bookmark Post in Technorati
Ответить с цитированием
Старый 27.01.2006, 10:41   #8
Gem
Пользователи
 
Регистрация: 23.01.2006
Сообщений: 8
По умолчанию

2 greeka,
Было бы интересно и полезно почитать эту книжку, захотелось скачать, но яндекс мне не помог.
Может кто даст ссылку?

Зато яндекс помог в другом, на одном из форумов было предложение по решению лабиринтов. Мне понятен этот алгоритм :clap: , а именно:
Hе реккурсивный. Пусть в матрице 1-стена,0-пусто. Ставим в начальной точке число 2. Далее просматриваем весь массив. Если встречаем пустую клетку, у которой соседняя клетка равна 2, то ставим в эту клетку число 3. Затем ещё раз просматриваем, но уже ищем 3, а ставим 4. Это продолжается до тех пор, пока не поставим число в клетку конца пути. Если за просмотр не сделано ни одного изменения, то значит пути не существует.В полученной матрице получить все кратчайшие пути - элементарно.
Матрица уже сформирована, осталось найти путь

Всем спасибо.
Gem вне форума  
Digg this Post!Bookmark Post in Technorati
Ответить с цитированием
Ответ


Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Вкл.



Текущее время: 22:16. Часовой пояс GMT.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd. Перевод: zCarot
Content Relevant URLs by vBSEO 3.5.0 RC2