Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Как создать алгоритм
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
imported_stayer imported_stayer вне форума
Member
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.06.2004
По умолчанию Как создать алгоритм - 08.06.2004, 17:28

Здравствуйте !!!
Хотел бы обратиться за помощью к господам магистрам, и это моя последняя надежда...
Мне необходимо реализовать алгоритм А* в Turbo Prolog для поиска оптимального пути на графе.
Данную задачу я бы смог сделать с помощью С++, но вот в Прологе просто ничего не получается, т.к. после многих лет программирования на обычных языках не могу я к этому Прологу никак привыкнуть и все тут... не могу никак смириться с его концепцией...
Народ, плиз, хелп !!!...
Ответить с цитированием
  (#2 (permalink)) Старый
Винитарх Винитарх на форуме
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,981
Сказал(а) спасибо: 2
Поблагодарили 303 раз(а) в 303 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 09.06.2004, 13:51

Какая именно эвристика приближения к цели нужна?
Ответить с цитированием
  (#3 (permalink)) Старый
imported_stayer imported_stayer вне форума
Member
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.06.2004
По умолчанию 09.06.2004, 15:11

Либо евклидово расстояние, либо "манхэттенское расстояние".
Без разницы.
Ответить с цитированием
  (#4 (permalink)) Старый
Mnior Mnior вне форума
Member
 
Сообщений: 487
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.12.2002
По умолчанию 09.06.2004, 15:22

Вот из лекций вырезано. Под проблему сам подстроишь:
Код:
aastar([[_,G,Node|Path]|_],[Node|Path],G):-
    final_state(Node).
aastar ([Path|Paths],Sol,G):-
    findall(NewPath,select_next_node(Path,NewPath),NewPaths),
    insert_each_path(NewPaths,Paths,Paths2),
    aastar(Paths2,Sol,G).
select_next_node([F,G,Node|Path],[F1,G1,Node1,F,G,Node|Path]):-
    succesor(Node,Node1),
    cost(Node,Node1,C),
    G1=G+C,
    heuristic(Node1,E),
    F1=G1+E,
    not(member(Node1,[Node|Path])).
Надо добавить:
"final_state" - это предикат (факт) с конечным(и) состоянием (узлом).
"succesor" - связи между состояниями (узлами).
"heuristic" - предикат вычисляющий "хорошесть" (эвристику) состояния (узла). Зависит от задачи.
"coast" - предикат вычисляющий "хорошесть" (эвристику) перехода из одного состояния (узла) в другое. Зависит от задачи.
Далее:
Код:
select_next_node([E,Node|Path],[E1,Node1,E,Node|Path]):-
    succesor(Node,Node1),
    heuristic(Node1,E1),
    not(member(Node1,[Node|Path])).

insert_each_path([],Paths,Paths).
insert_each_path([Path|Paths],Paths2,Paths3):-
    inserare_1_Path(Path,Paths2,Paths4),
    insert_each_path(Paths,Paths4,Paths3).

insert_1_path(Path,[],[Path]).
insert_1_path([E|Path],[[E2|Path2]|Paths],[[E|Path],[E2|Path2]|Paths2]):-
    E<=E2.
insert_1_path([E|Path],[[E2|Path2]|Paths],[[E2|Path2]|Paths2]):-
    E>E2,
    insert_1_path([E|Path],Paths,Paths2).
Остальные предикаты известны.
Думаю декларации сам запишешь. (и предикат "member").

Цитата:
Originally posted by stayer
[b]... никак привыкнуть и все тут ... не могу никак смириться с его концепцией...
Привыкнуть ладно, но что в его "концепции" тебе не нравится?
Ответить с цитированием
  (#5 (permalink)) Старый
Mnior Mnior вне форума
Member
 
Сообщений: 487
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.12.2002
По умолчанию 09.06.2004, 15:37

Цитата:
Originally posted by stayer
[b]Либо евклидово расстояние, либо "манхэттенское расстояние".
Без разницы.
В графе?
А как он задан? С указанием координат?
Если да, то для близости, можно так:
Код:
heuristic(Node, Heur):-
    final_state(FinNode),
    pologenie(FinNode,FX,FY),
    pologenie(Node,X,Y),
    Heur = sqrt((X-FX)*(X-FX)+(Y-FY)*(Y-FY)).
А для "короткости" маршрута можно так:
Код:
coast(Node,Node1,C):-
    pologenie(Node,X,Y),
    pologenie(Node1,X1,Y1),
    C = sqrt((X-X1)*(X-X1)+(Y-Y1)*(Y-Y1)).
Конечно всё это можно проминимизировать (упростить), но это сам.
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Винитарх Винитарх на форуме
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,981
Сказал(а) спасибо: 2
Поблагодарили 303 раз(а) в 303 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 10.06.2004, 18:51

Mnior.
А если граф задан не координатами, а длиной дуг (как в нашем метро)?
Какую здесь эвристику приближения к цели выбрать, как мыслишь?
Ответить с цитированием
  (#7 (permalink)) Старый
imported_stayer imported_stayer вне форума
Member
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.06.2004
По умолчанию 10.06.2004, 20:16

Спасибо, ребята, реально помогли
К сожалению вот кроме как спасибой отблагодарить по-другому сложно...

Цитата:
Привыкнуть ладно, но что в его "концепции" тебе не нравится?
В процедурных языках указывается как я хочу получить данные, а в логических - какие.

Если честно, то после того, как окончится у нас курс систем искусственного интеллекта, мечтаю поскорее забыть о Turbo Prolog как о кошмарном сне... и больше никогда к нему не возвращаться и всячески избегать повторной встречи с ним...
Ответить с цитированием
  (#8 (permalink)) Старый
Mnior Mnior вне форума
Member
 
Сообщений: 487
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 19.12.2002
По умолчанию 11.06.2004, 02:46

Цитата:
Originally posted by Винитарх
[b]Mnior.
А если граф задан не координатами, а длиной дуг (как в нашем метро)?
Какую здесь эвристику приближения к цели выбрать, как мыслишь?
Если стремится к минимальному пути, то просто "coast" считать (ссумировать дуги), а "heuristic" можно послать куда подальше.
А к чему это?

Цитата:
Originally posted by stayer
[b]Если честно, то после того, как окончится у нас курс систем искусственного интеллекта, мечтаю поскорее забыть о Turbo Prolog как о кошмарном сне... и больше никогда к нему не возвращаться и всячески избегать повторной встречи с ним...
Правильно, переходи на Visual Prolog. А Си и Pascalь забудь, как зря потраченное на фигню время.

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

Надеюсь, ты, всё таки, имел ввиду другое.
Ответить с цитированием
Ads
Ответ

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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как создать в интерфейсе кнопку "Создать проект" в Visual Basic2010 imported_Fred_ Вопросы начинающих программистов 0 11.03.2011 17:50
Создать алгоритм вычисления систем электропитания Lerik Вопросы начинающих программистов 4 21.01.2011 01:31
алгоритм snegov1k Задания за деньги 1 22.05.2010 23:27
Алгоритм Дейкстры fredwriter Pascal 3 09.05.2010 02:48
Как создать алгоритм LZW Jenton Общие вопросы создания ПО 1 15.12.2009 18:26
Переборный алгоритм как его создать Y_Vetal Алгоритмы 3 28.02.2009 10:56
Алгоритм Crypt на MD5 Mnior C++ на Unix 5 13.02.2007 20:04
Как создать алгоритм работы программы nurich C++ Builder 2 15.11.2006 03:29
Алгоритм Бута ускоренный алгоритм умножения чисел MrPIT Алгоритмы 0 20.05.2006 18:12
Создать алгоритм генерации Множество Булеана Nikolai Вопросы начинающих программистов 3 31.12.2005 15:35
Код программы на Visual Prolog Алгоритм Флойда и Алгоритм Дейкстры r Вопросы начинающих программистов 2 08.12.2005 00:34
Интересная задача как создать алгоритм данных на вычисление ЕкатеринаАК Алгоритмы 8 06.12.2005 12:07



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов