Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Работа Новый топик    Ответить
Топик располагается на нескольких страницах: 1 2      [все]
 Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Уважаемые коллеги!

Для проведения некоторых расчетов, мне нужна программа, решающая Задачу китайского почтальона.
Причем, не обязательно исходный текст.
Мне достаточно иметь исполняемый файл и инструкцию по его использованию для расчетов.
Мне известно, что задачи, типа указанной, чаще решают на С++.
Поэтому я решил обратиться к участникам данного форума.
Более того, совершенно не обязательно, чтобы программа была на С++.
Подойдет любая работоспособная программа.
Например, есть соответствующая программа https://github.com/supermitch/Chinese-Postman
Она написана на Python.
Но запустить ее я не могу.
На форуме по Python, мне порекомендовали обратиться на форум по программированию.
Всем, кто поможет мне - большое спасибо...
11 июл 20, 18:32    [22165772]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
mayton
Member

Откуда: loopback
Сообщений: 48016
Как ты ее запускал? Какая была ошибка?
11 июл 20, 18:41    [22165774]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
mayton,

Я ее запускал, как написано в инструкции

python main.py north
11 июл 20, 18:44    [22165776]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
mayton,

Питон можно вызывать из любого местоположения. Я это учел
11 июл 20, 18:46    [22165777]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 50835

UAP
Питон можно вызывать из любого местоположения. Я это учел

А установить его не забыл?..

Posted via ActualForum NNTP Server 1.5

11 июл 20, 18:47    [22165779]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
mayton
Member

Откуда: loopback
Сообщений: 48016
UAP
mayton,

Я ее запускал, как написано в инструкции

python main.py north

Я повторю вопрос. Какой код ошибки ты видел?

Ошибка может быть связана с неверной версией Python.
11 июл 20, 18:49    [22165780]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Dimitry Sibiryakov,

Я, вначале, установил самый новый Питон.
Ничего.
Затем я прочитал, что программа сделана для Питон 2.7

This program will probably run in Python 2.7 and Python 3.4-3.7. (Tested recently w/ Python 3.7.2)

Скачал, поставил.
Выглядит все иначе, но блымает и исчезает.
11 июл 20, 18:49    [22165782]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
mayton,

Я не сразу, но установил правильную версию
11 июл 20, 18:51    [22165783]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 50835

UAP
блымает и исчезает

А ты не запускай двойным кликом, ты по-старинке, из командной строки.

Posted via ActualForum NNTP Server 1.5

11 июл 20, 18:56    [22165787]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Dimitry Sibiryakov,

Я пробовал всеми известными мне способами.
Даже из командной строки ТС64
11 июл 20, 18:58    [22165788]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 50835

Значит не судьба. Блыматор у тебя неотключаемый.

Posted via ActualForum NNTP Server 1.5

11 июл 20, 19:08    [22165791]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
mayton
Member

Откуда: loopback
Сообщений: 48016
Блымает. И исчезает. Вот такие симптомы. Что скажете, коллеги. Я щас - с мобильного пишу.

Фиг проверишь.
11 июл 20, 19:08    [22165792]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Может быть есть другие программы?
Именно на С++
Может быть кто-то писал такую курсовую?
Хотя, насколько я могу судить, задачи на графах, почти всегда, очень сложные.
В недрах Задачи о китайском почтальоне сидит алгоритм Флёри, который вообще понять невозможно...
11 июл 20, 19:11    [22165794]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Было бы просто великолепно, если бы особенно опытные участники обсуждения, действительно, попробовали запустить сами.
Очень может быть, что я допускаю глупую ошибку...
11 июл 20, 19:13    [22165795]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Вот тут:
http://scask.ru/j_book_graph.php?id=94
есть алгоритм и пример для решения (5.2. и далее).
Пользоваться таким сайтом очень неудобно, но мне удалось пробиться.
И на последнем абзаце примера я застрял.
Фактически нужен алгоритм поиска цикла Эйлера для мультиграфа.
Даже на словах я не понимаю, как такое писать...

Модератор: Тема перенесена из форума "C++".


Сообщение было отредактировано: 11 июл 20, 21:01
11 июл 20, 19:21    [22165797]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
Нестандартное мышление
Member

Откуда:
Сообщений: 88
UAP,

Сделай батник, в нем пропиши запускаемую строку
И в конце pause
Смотри что тебе схлапывание пишет в консоли
11 июл 20, 21:20    [22165815]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Нестандартное мышление,

Спасибо, обязательно попробую.

Это первый дельный совет!!
11 июл 20, 21:30    [22165818]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Вот, что дает батник

К сообщению приложен файл. Размер - 26Kb
11 июл 20, 21:39    [22165822]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
Алексей Роза
Member [заблокирован]

Откуда: РФ
Сообщений: 557
а так делали?

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

Сообщение было отредактировано: 11 июл 20, 21:41
11 июл 20, 21:39    [22165823]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Алексей Роза,
Да, делал
Везде приводятся программы, которые непонятно как запустить
Вы видели, что я обращался на форум по С++, так модератор меня перебросил в данный форум
11 июл 20, 21:44    [22165826]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Нестандартное мышление,

Вот, что сделала программа без батника.
Я еле успел кликнуть, чтобы остановить:

К сообщению приложен файл. Размер - 29Kb
11 июл 20, 21:46    [22165827]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Явно что-то считает.
Но куда пишет?
11 июл 20, 21:47    [22165829]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
Нестандартное мышление
Member

Откуда:
Сообщений: 88
UAP,
надо в реестре прописать путь к питону в PATH
либо указать полный путь в батнике к исполняемому файлу
11 июл 20, 21:49    [22165831]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Нестандартное мышление,

Это делается птичкой при установке Питона.
Но я сейчас попробую
11 июл 20, 21:50    [22165832]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
Нестандартное мышление
Member

Откуда:
Сообщений: 88
UAP
Вот, что дает батник

из того места где запускаешь батник - питона не видно
11 июл 20, 21:51    [22165836]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Нестандартное мышление,

Вы правы!!

В инталляторе наврали!!

Вот, что получилось:

К сообщению приложен файл. Размер - 58Kb
11 июл 20, 22:01    [22165844]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Это уже очень похоже на то, что мне нужно...

Теперь нужно понять, как готовить исходные данные
11 июл 20, 22:02    [22165845]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Нестандартное мышление,

Большое спасибо за помощь!

Буду изучать программу дальше.
Обязательно сообщу, что будет получаться.
Если потребуется опять обращусь за помощью
11 июл 20, 22:09    [22165847]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
Нестандартное мышление
Member

Откуда:
Сообщений: 88
UAP,
Я делал похожую программу в институте на С голом
С визуализацией в DOS

Дешевле было искать кратчайший путь от конца графа к началу.
автор
то есть перебором считались все возможные суммы веса пути от конца к началу и в итоге выбирался минимальный


Сообщение было отредактировано: 11 июл 20, 23:08
11 июл 20, 23:02    [22165864]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
Алексей Роза
Member [заблокирован]

Откуда: РФ
Сообщений: 557
UAP
Вы видели, что я обращался на форум по С++, так модератор меня перебросил в данный форум

ну потому что у вас в сообщении питон. И по ссылке питон. И обсуждают все питона.
12 июл 20, 00:15    [22165883]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Алексей Роза,

Я обращался на форум по Питону, они меня направили на С++.
С++ поговорили и модератор меня перекинул сюда))
12 июл 20, 14:40    [22166020]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
mayton
Member

Откуда: loopback
Сообщений: 48016
И знаешь почему перекинул?
12 июл 20, 14:47    [22166026]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
Нестандартное мышление,

Вам особая благодарность!
Вы подсказали пару штрихов, которые определили исход моих поисков.
Я уже могу пользоваться программой.
Опишу методику, если кому-либо будет нужно.
Для подготовки исходных данных нужно в текстовом редакторе открыть файл data из папки data.
Там, по образу и подобию "секций" создать свою секцию, содержащую изучаемый граф.
Секции нужно дать имя, например xyzt.
Это же имя используется вместо имени north в вызове программы.

Нестандартное мышление,
не могли бы вы выложить ваше решение и прокомментировать его?
Вам еще раз большое спасибо!
12 июл 20, 14:48    [22166028]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
mayton,

Вы здесь!
Почему?
12 июл 20, 14:49    [22166032]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
mayton
Member

Откуда: loopback
Сообщений: 48016
Потому что тема кодинга С++ была не раскрыта, мой упрямый друг.

Точно также как и алгоритмов. У тебя просто не было по сути никаких вопросов кроме того
как "запускать" и спецэффектов консоли.

Вот ты и оказался в Работе.
12 июл 20, 15:13    [22166050]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
UAP
Member

Откуда:
Сообщений: 493
mayton,

Ладно, пусть будет так.
Главное, что задача решена.
Кроме того, возможно, покажут код на С более эффективного решения.
12 июл 20, 15:18    [22166055]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
Нестандартное мышление
Member

Откуда:
Сообщений: 88
UAP

Нестандартное мышление,
не могли бы вы выложить ваше решение и прокомментировать его?
Вам еще раз большое спасибо!


Это было 25 лет назад
В кратце:
Просчитывались все возможные пути от конечной точки до начальной и заносились в массив с весом каждого пути и точками маршрута
Затем поиск минимальной суммы веса пути
Затем вывод этого массива в обратном порядке

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

еще вспомнил
при просчете вариантов прохода графа от конечной точки до начальной исключаются лишние операции на расчет ненужных операций, которые не приводят к нужной конечной точке



Сообщение было отредактировано: 12 июл 20, 18:33
12 июл 20, 18:26    [22166099]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
mayton
Member

Откуда: loopback
Сообщений: 48016
UAP
mayton,

Ладно, пусть будет так.
Главное, что задача решена.
Кроме того, возможно, покажут код на С более эффективного решения.

Код на С будет просто быстрее работать. Можем джентльменское пари заключать сразу.
Я сравнивал Python с "С" под нагрузкой. И результаты пока - очень печальные. Для Питона.

Это имелось в виду под "эффективностью"?
12 июл 20, 18:53    [22166107]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
vikkiv
Member

Откуда: London
Сообщений: 2704
mayton,

ну так, C компилированный а Python скриптовый (интерпретированный, по дороге с парсингом, "оптимизациями" и пр. прелестями прежде чем до шага компиляции дойдёт) в машинный код (с десятками тысяч отдельных промежуточных библиотек на всякий вкус) - причём через ту-же группу C языков между прочим.

конечно в живую на ходу если делать то латентность адовая в основном получается, по оптимальности тоже большие вопросы в итоге (уж за паралельность/мультипоточность - так вообще тёмный лес часто)

Сообщение было отредактировано: 12 июл 20, 19:57
12 июл 20, 19:54    [22166123]     Ответить | Цитировать Сообщить модератору
 Re: Программа, решающая Задачу китайского почтальона  [new]
Алексей Роза
Member [заблокирован]

Откуда: РФ
Сообщений: 557
ещё про расходы можно вспомнить
в PHP, например, int занимает не 4 байта, а 40.
массив ваще ад.
12 июл 20, 23:06    [22166160]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2      [все]
Все форумы / Работа Ответить