?

Log in

No account? Create an account

Entries by tag: problems

задачки
пакман
_navi_

За время конференций я придумал пару „исследовательских” задачек, решения которых мне пока не очевидны. Beware: первая из них слишком неформальная.

Задача о языках

Имея заданное натуральное число n, определить набор из n естественных языков, таких что возможность понимать фразы на неизвестных тебе языках максимальна.

Другое возможное требование: набор должен быть таким, чтобы изучение следующих языков из соответствующих наборов из n+1, n+2, …, N языков было наиболее простым. (То есть, надо строго упорядочить набор языков, так чтобы любой хвост этого списка было „максимально просто” изучать)

Задача туриста

Предположим, у нас есть граф, представляющий собой карту города: вершины это перекрёстки и “points of interest”, а рёбра — это соединяющие их улицы. Одна из вершин — отель, в котором живёт турист. Надо составить d путей длиной не больше l, таких что все они начинаются и заканчиваются в вершине „отель” и покрывают максимальное (в каком-либо определённом смысле) количество интересных точек или наибольшую часть города.

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

Эта задача чем-то напоминает TSP, но тут нам надо построить несколько путей. Правда, можно подумать, можно ли свести это к поиску одного пути в модифицированном графе.

Вместе с этой задачей также стоит решать следующую практическую задачу: имея картинку с картой города из Google Maps, построить граф улиц/перекрёстков.