вторник, 08 ноября 2011
22:15

Задача по Prolog

все записи пользователя в сообществе [AtalantA]
Какого дьявола ты убил дьявола?!
Помогите, пожалуйста, решить:
Даны остановки, между которыми могут ходить автобусы, троллейбусы и трамваи. Дано время прохождения транспорта между остановками и время ожидания транспорта на остановке. Найти минимальное время поездки между двумя заданными остановками.
Желательно код с комментариями.

@темы: Вопрос, Prolog

URL
Комментарии
08.11.2011 в 22:26

Flex Ferrum
IDDQD - Команда молодости нашей, команда, без которой мне не жить.
Здесь есть несколько полезных ссылок. :)
URL
08.11.2011 в 22:34

Mr.Freedom
Ну, пробьешь ты головой стену. И что ты будешь делать в соседней камере?
Flex Ferrum, +1 к троллингу))
URL
08.11.2011 в 22:39

Flex Ferrum
IDDQD - Команда молодости нашей, команда, без которой мне не жить.
Flex Ferrum, +1 к троллингу))
Ну, найти спеца, который сходу напишет (на прологе) алгоритм решения задачи поиска кратчайшего пути на графе сейчас не так просто. Проще найти сам исходник и подрихтовать под себя. ;)
URL
08.11.2011 в 22:52

Mr.Freedom
Ну, пробьешь ты головой стену. И что ты будешь делать в соседней камере?
Flex Ferrum, тру мужики пишут с нуля) на прологе не писал - кратчайшие пути - делал конечно...
URL
09.11.2011 в 13:45

alba-longa
На свете есть всего 10 разновидностей людей. Те, которые понимают бинарный код, и те, кто не понимают
И откуда такая задача, если не секрет? Специальность, дисциплина, курс?
ИМХО, тянет примерно на курсовую или экзаменационную задачу.
Кстати, Вы в курсе, что у пролога много версий и они, внезапно, отличаются? Я к тому, что даже если кто-то добрый напишет сюда код с комментариями, почти наверняка он не запустится. Единственный вариант смотреть примеры и пытаться применить их к своей конкретной задаче.
URL
09.11.2011 в 16:52

Mr.Freedom
Ну, пробьешь ты головой стену. И что ты будешь делать в соседней камере?
alba-longa, а симпекс методом не решается?
URL
09.11.2011 в 17:38

alba-longa
На свете есть всего 10 разновидностей людей. Те, которые понимают бинарный код, и те, кто не понимают
Mr.Freedom, да фиг знает, я им не пользовалась лет 8. Но не думаю, что на прологе его проще программировать. А так это обычная задача на граф.
URL
09.11.2011 в 17:42

Mr.Freedom
Ну, пробьешь ты головой стену. И что ты будешь делать в соседней камере?
alba-longa, ага - в общем случае по моей памяти не имеет решенияXDD
URL
09.11.2011 в 18:57

alba-longa
На свете есть всего 10 разновидностей людей. Те, которые понимают бинарный код, и те, кто не понимают
Mr.Freedom, в общем случае не имеет алгоритма решения полиномиальной сложности. Полным перебором можно решить любую задачу :)
URL
09.11.2011 в 19:18

Mr.Freedom
Ну, пробьешь ты головой стену. И что ты будешь делать в соседней камере?
alba-longa, по поводу полного перебора вас ждут плохие новости: время не дискретно) Именно в этой задаче перебор есть хоть и жуткий(экспоненциальный кажется)
А вообще если инетересно почитайте вот это: mathemlib.ru/mathenc/item/f00/s00/e0000152/inde... - самое интересное про маркова-поста, с первого взгляда там тоже кажется что есть перебор... а его нет=)
URL
09.11.2011 в 19:25

alba-longa
На свете есть всего 10 разновидностей людей. Те, которые понимают бинарный код, и те, кто не понимают
Mr.Freedom, как бы я знаю, что задача коммивояжера является NP-полной. И чем отличается детерминированная машина Тьюринга от недетерминированной, тоже.
Полным перебором можно решить _любую_ задачу в теории. Но я ничего не сказала о времени, которое потребуется на это решение :)
URL
09.11.2011 в 19:30

Mr.Freedom
Ну, пробьешь ты головой стену. И что ты будешь делать в соседней камере?
Теорема(Марков-Пост) существует полугруппа, в которой проблема распознавания равенства слов алгоритмически неразрешима. (из моего учебника по дискретной математике=) )
А под перебором вы подразумеваете конечность этого перебора?
И кстати тоже интересная задача - есть трасса, есть машина нужно понять с какой траекторией лучше всего двигаться зная всякие параметры машины. Там народ решает до кучи диффуров и только после этого делает какие то предположения. Тут уж никакой перебор не светит - это не граф.
URL
09.11.2011 в 20:26

alba-longa
На свете есть всего 10 разновидностей людей. Те, которые понимают бинарный код, и те, кто не понимают
Mr.Freedom, можно ссылку на учебник? Желательно с номером страницы. А то не очень понятно, какую конкретно задачу вы имеете в виду.
Да, конечность перебора. Разумеется, это относится только к дискретизированным данным. И задача с машиной тоже может быть решена приближенно перебором, просто вычислений для этого потребуется огого (если перебирать абсолютно все возможные варианты). Решение диффуров уменьшает количество вариантов до решабельного.
URL
09.11.2011 в 20:31

Mr.Freedom
Ну, пробьешь ты головой стену. И что ты будешь делать в соседней камере?
www.kodges.ru/42843-diskretnaya-matematika-dlya...
вот здесь учебник, глава 2.2 алгебры с одной операцией.
URL
19.12.2011 в 19:17

[AtalantA]
Какого дьявола ты убил дьявола?!
ОМГ, где-то с середины я перестала понимать, о чем вы :facepalm: Йа блондинко Т___Т
URL