Когда-то я узнал о неплохой и очень быстрой аппроксимации решения задачи коммивояжера. Предлагается построить минимальное остовное дерево графа. Это делается очень быстро, буквально линейно по количеству рёбер.
А затем обходим его вокруг, как бы по периметру. Все ребра при этом будут пройдены дважды. Но можно будет срезать путь, когда следующая по плану не листовая, и мы её уже посещали. Поскольку путь коммивояжера тоже является остовным деревом, то его длина не превосходит сумму длин рёбер дерева минимального, которое в худшем случае мы обойдём дважды.
В итоге результат будет не более чем в два раза хуже оптимального.
Ну мы опять по кругу ходим. Дроби -- это как числа, противоположные натуральным -- способ объяснить ребенку на пальцах то, что и так почти понятно. Но не определение. Вот надо три пиццы на четверых разделить, мы и разрезаем каждую на четыре части и берём по три куска.
До того, как определены рациональные числа, уравнение 2x=1 не имеет решений. После того, как мы ввели рациональные числа как множество классов эквивалентности над парами целых, ввели операции, доказали корректность этих определений (независимость от выбора представителя класса) вот тогда уже можно сказать "а давайте вместо кортежа (a, b) будем писать a/b и назовем эту запись обыкновенной дробью". Тогда можно решать новые уравнения и так далее.
Точно так же не получится определить алгебраические числа, как корни полиномов. До введения вещественных чисел уравнение x²=2 не имеет решений. Не получится определить квадратный корень как несамостоятельную операцию. Сначала вводим вещественные числа, потом радуемся, что в них больше уравнений решается. Но всё ещё не все.
Надо ли упомянуть, что комплексная мнимая единица не определяется, как квадратный корень из -1?..
Нет, когда я учился в шестом классе, интернет был еще не тот, тогда больше книжки читали:) если хотите почитать Википедию, то вот: Формальное определение.
Не очень понятно, что значит не самостоятельная операция. Теория чисел вводит определения последовательно, и логично предположить, что очередные определения могут ссылаться только на те, которые уже есть на данный момент. Если у вас есть целые числа и умножение на них, вы, бесспорно, можете написать уравнение 2x=1, только оно тоже не будет иметь решения. Это тупик.
На самом деле если ту же википедию проскролить чуть дальше содержания, там будет "формальное определение", которое не страдает этой проблемой.
Так же как в школе когда-то давали "определение" целым как "натуральные, им противоположные и ноль". Нету у натуральных чисел противоположных, так как нет вычитания. Уравнение x+5=3 вполне понятно в натуральных, но не имеет там решений. Целые числа определяются через натуральные по аналогии с тем, как рациональные через целые. Вот только в шестом классе, когда часть "математики" начала гордо зваться "алгеброй", это можно было объяснить далеко не всем.
Ох, ничего себе понаписали комментариев за два дня! Старался их прочитать, чтобы не повториться. Мне понравилась цепочка определений -- вещественные, как рациональные с иррациональными, а иррациональные -- как вещественные без рациональных. Вернее не цепочка, а колечко..
Про бесконечность записи, и что там число, а что не число. 1 -- тоже не число, а его запись. Даже рациональные числа вообще не записать нормально. Не верьте определению Википедии, нельзя определять их через "обыкновенную дробь", так как на целых числах нет операции деления.
А если серьёзно, то я не понял посыла. Зря называем вещественными? Нет, не зря. Это приближение которого хватает в подавляющем большинстве задач. Например константа "пи" с точностью double позволяет вычислить длину окружности заданного диаметра для практически любой задачи. Дальше уже символьные вычисления -- но это отдельная тема.
Информация
В рейтинге
Не участвует
Откуда
Санкт-Петербург, Санкт-Петербург и область, Россия
Когда-то я узнал о неплохой и очень быстрой аппроксимации решения задачи коммивояжера. Предлагается построить минимальное остовное дерево графа. Это делается очень быстро, буквально линейно по количеству рёбер.
А затем обходим его вокруг, как бы по периметру. Все ребра при этом будут пройдены дважды. Но можно будет срезать путь, когда следующая по плану не листовая, и мы её уже посещали. Поскольку путь коммивояжера тоже является остовным деревом, то его длина не превосходит сумму длин рёбер дерева минимального, которое в худшем случае мы обойдём дважды.
В итоге результат будет не более чем в два раза хуже оптимального.
Извините косноязычность.
Ну мы опять по кругу ходим. Дроби -- это как числа, противоположные натуральным -- способ объяснить ребенку на пальцах то, что и так почти понятно. Но не определение. Вот надо три пиццы на четверых разделить, мы и разрезаем каждую на четыре части и берём по три куска.
До того, как определены рациональные числа, уравнение 2x=1 не имеет решений. После того, как мы ввели рациональные числа как множество классов эквивалентности над парами целых, ввели операции, доказали корректность этих определений (независимость от выбора представителя класса) вот тогда уже можно сказать "а давайте вместо кортежа (a, b) будем писать a/b и назовем эту запись обыкновенной дробью". Тогда можно решать новые уравнения и так далее.
Точно так же не получится определить алгебраические числа, как корни полиномов. До введения вещественных чисел уравнение x²=2 не имеет решений. Не получится определить квадратный корень как несамостоятельную операцию. Сначала вводим вещественные числа, потом радуемся, что в них больше уравнений решается. Но всё ещё не все.
Надо ли упомянуть, что комплексная мнимая единица не определяется, как квадратный корень из -1?..
Нет, когда я учился в шестом классе, интернет был еще не тот, тогда больше книжки читали:) если хотите почитать Википедию, то вот: Формальное определение.
Не очень понятно, что значит не самостоятельная операция. Теория чисел вводит определения последовательно, и логично предположить, что очередные определения могут ссылаться только на те, которые уже есть на данный момент. Если у вас есть целые числа и умножение на них, вы, бесспорно, можете написать уравнение 2x=1, только оно тоже не будет иметь решения. Это тупик.
На самом деле если ту же википедию проскролить чуть дальше содержания, там будет "формальное определение", которое не страдает этой проблемой.
Так же как в школе когда-то давали "определение" целым как "натуральные, им противоположные и ноль". Нету у натуральных чисел противоположных, так как нет вычитания. Уравнение x+5=3 вполне понятно в натуральных, но не имеет там решений. Целые числа определяются через натуральные по аналогии с тем, как рациональные через целые. Вот только в шестом классе, когда часть "математики" начала гордо зваться "алгеброй", это можно было объяснить далеко не всем.
Ох, ничего себе понаписали комментариев за два дня! Старался их прочитать, чтобы не повториться. Мне понравилась цепочка определений -- вещественные, как рациональные с иррациональными, а иррациональные -- как вещественные без рациональных. Вернее не цепочка, а колечко..
Про бесконечность записи, и что там число, а что не число. 1 -- тоже не число, а его запись. Даже рациональные числа вообще не записать нормально. Не верьте определению Википедии, нельзя определять их через "обыкновенную дробь", так как на целых числах нет операции деления.
А если серьёзно, то я не понял посыла. Зря называем вещественными? Нет, не зря. Это приближение которого хватает в подавляющем большинстве задач. Например константа "пи" с точностью double позволяет вычислить длину окружности заданного диаметра для практически любой задачи. Дальше уже символьные вычисления -- но это отдельная тема.