Теория графов., Раскраска карты минимальным кол_вом цветов |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Теория графов., Раскраска карты минимальным кол_вом цветов |
-StrangerFX- |
Сообщение
#1
|
Гость |
Программа раскрашивания карты минимальным количеством цветов.
Исходные данные: - Список регионов с указанием соседей каждого региона. Выходные данные: - Список регионов с приписанными им цветами. - Общее число использованных цветов. Требованния к фунуциональности: - Эфективность решения. - Наглядный вывод результата(раскраска карты). - Опционально редактор карт(с возможностью рисовать мышью). Вопрос следуюший, как сделать редактор карт с возможностью рисования мышью и удомным для пользователя меню. |
Lapp |
Сообщение
#2
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Гость, ты много всего перечислил, и не совсем понятно, насколько тебя волнует основной алгоритм - процесс раскрашивания. Если волнует, то могу помочь с этим. Задача очень любопытная, меня заинтересовало уже то, что проблема четырех красок как раз не так давно была решена теоретически (с помощью компьютера, это как бы наглядный пример, как комп помогает в чистой математике), и захотелось самому прикоснуться..
Я тут набросал прогу, которая производит правильную (то есть соседние области - разноцветные) раскраску, не гарантируя минимальности количества цветов. Основной принцип - рекуррентная окраска областей. Написано без ООП, да и вообще довольно просто. Надеюсь, разберешься. А уж минимальность обеспечивай сам.. (можешь задавать вопросы) const А вот пример файла с областями, reg_nei.dat Код 5 2 3 4 5 6 3 1 3 6 3 1 2 4 3 1 3 5 3 1 4 6 3 1 5 2 Это расположение представляет собой пятилепестковую ромашку . На нем (и на более простых) я проверял прогу. Вроде, не врет.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 3.05.2024 2:16 |