Как стать автором
Обновить

Переход от приближенного решения к точному: задача о разбиении квадрата на 50 подобных остроугольных треугольников

Время на прочтение 3 мин
Количество просмотров 15K
Блог компании Wolfram Research Программирование *Математика *
Перевод


Перевод поста Эда Пегга младшего (Ed Pegg Jr) "From Close to Perfect—A Triangle Problem"
Выражаю благодарность за помощь в переводе Андрею Дудину.
Скачать перевод в виде документа Mathematica, который содержит весь код использованный в статье, можно здесь.


В языке Wolfram Language (доступном, скажем, в системе Mathematica) функция RootApproximant позволяет найти замкнутую форму в виде алгебраического числа для некоторого приближённого числа, и эта функция позволила нам превратить приближенное решение задачи о разбиении квадрата на 50 подобных остроугольных треугольников с углами (45°, 60°, 75°) в точное.

Ясно, что квадрат можно разбить на треугольники (триангулировать), например, просто соединив его противоположные вершины. Известно, так же, что квадрат можно разбить на семь подобных треугольников разной площади или на десять остроугольных равнобедренных треугольников (см. рис. ниже). Известны также классические задачи, связанные с разбиением квадрата на восемь остроугольных треугольников (см. рис. ниже), или на двадцать треугольников со сторонами, относящимися друг к другу как Perehod-ot-priblizhjonnogo-reshenija-k-tochnomu-zadacha-o-razbienii-kvadrata-na-50-podobnyh-ostrougolnyh-treugolnikov_1.png. На третьем чертеже (считая сверху) показано разбиение квадрата на подобные треугольники с углами (45°, 60°, 75°), но вы можете с легкостью заметить, что это решение не корректно, так как один из треугольников немного накладывается на другой.
Читать дальше →
Всего голосов 44: ↑42 и ↓2 +40
Комментарии 5

Задача коммивояжера (TSP) точное решение — метод динамического программирования

Время на прочтение 9 мин
Количество просмотров 9.3K
Python *Алгоритмы *

Задача коммивояжёра – одна из интереснейших подзадач комбинаторной оптимизации. Впервые мне пришлось с ней столкнуться, работая над логистической системой торгового предприятия.

Решение методом грубой силы не подходило из-за вычислительной сложности. Была предпринята попытка реализовать метод ветвления и границ с отсечением в глубину. В целом, подход себя оправдывал, но иногда при некоторых специфических входных данных алгоритм выдавал решение далёкое от оптимального.

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

Читать далее
Всего голосов 10: ↑10 и ↓0 +10
Комментарии 16

Задача коммивояжера (TSP) точное решение — метод ветвей и границ

Время на прочтение 17 мин
Количество просмотров 11K
Python *Алгоритмы *C *

Что делает код хорошим? Большинство программистов ответят: хороший код должен быть структурирован, легко читаем и понятен. Но так ли важно качество кода, если он медленный? В большинстве задач производительность кода не критична, хотя и желательна. Но есть задачи, время выполнения которых столь огромно, что выигрыш в производительности доминирует над всем остальным.

Я говорю про NP-трудные задачи (NP-трудность - недетерминированная полиномиальная трудность по времени) и на одной из данного класса хочу акцентировать ваше внимание. Задаче коммивояжера.

Мы не будем рассматривать эвристические алгоритмы, нам нужно точное решение.

Читать далее
Всего голосов 32: ↑32 и ↓0 +32
Комментарии 42

Задача коммивояжера (TSP) точное решение — метод целочисленного линейного программирования (Integer programming)

Время на прочтение 20 мин
Количество просмотров 17K
Высокая производительность *Python *Совершенный код *Алгоритмы *

Дочитав эту статью до конца, вы сможете решать точно задачу коммивояжёра на сотню элементов за считанные секунды!

Заинтригованы? Тогда, добро пожаловать под кат.

Читать далее
Всего голосов 124: ↑124 и ↓0 +124
Комментарии 40