lrs - онлайн у хмарі

ПРОГРАМА:

ІМ'Я

lrslib - Перетворення між представленнями опуклих многогранників.

СИНТАКСИС

лр input.ine

лр input.ine | lrsbuffer

Ірсфур'є file.ine [файл]

зайвий input.ine

ОПИС

Багатогранник можна описати списком нерівностей (H-представництво) або за списком
його вершин і крайніх променів (V-представництво). лр це програма на C, яка перетворює a
H-представлення багатогранника до його V-подання, і навпаки. Ці проблеми
відомі відповідно на вершина перерахування та опуклий корпус проблеми.

Фукуди FAQ сторінка[1] містить більш детальний вступ до проблеми, поряд з
багато корисних порад для нового користувача.

lrsbuffer можна видалити деякі дублікати виводу. зайвий знаходить зайві нерівності в
Вхід

Фото ФОРМАТИ

Формати файлів були розроблені спільно з Komei Fukuda і сумісні з CDD[2].

Вхідні дані для лр є H- або V-поданням багатогранника.

ім'я
{рядок репрезентації}
{опції}
{лінійності[3]}
починати
мн раціональний
{вхідна матриця}
кінець
{опції}

ім'я – це ім’я, надане користувачем для багатогранника. Коментарі можуть з'являтися перед початком або
після закінчення, і щоб уникнути тлумачення як варіант, слід починати зі спец
символ, наприклад "*" або "#".

ім'я – це ім’я, надане користувачем для багатогранника. подання лінія є також
«H-представлення» або «V-представлення». Якщо опущено, передбачається H-представництво. The
вхідні коефіцієнти зчитуються у вільному форматі і не перевіряються на тип. Коефіцієнти є
розділені пробілом. m – кількість рядків, а n – кількість стовпців у вхідних даних
матриця.

Н-представництво
Ціле число m - це кількість нерівностей, а ціле число n - розмірність
введіть +1. Список нерівностей містить коефіцієнти нерівностей виду

a0 + a1x1+ ... + an-1 xn-1 >= 0.

Ця нерівність вводиться як пряма

a0 a1... an-1

Коефіцієнти можна вводити у вигляді цілих чи раціональних чисел у форматі x/y.

V-представництво
Ціле число m - це кількість вершин і променів, а ціле число n - розмірність
вхід +1. Кожна вершина задається у вигляді

1 v0 v 1... vn-1

Кожен промінь подано у формі

0 r0 r 1... rn-1

де r0 r 1... rn-1 — точка на промені.

У кожному файлі має бути принаймні одна вершина. Для обмежених многогранників не буде
увійшли промені. Коефіцієнти можна вводити у вигляді цілих чи раціональних чисел у форматі x/y.

Примітка: та цінності CDD користувачі: лр використовує по суті той самий формат файлу, що і CDD. Підготовлені файли для
CDD має працювати з невеликими змінами або без них. Зверніть увагу, що V-подання
відповідає опції «корпус» в CDD. Специфічні параметри CDD можна залишити на вході
файлів і буде ігноруватися лр. Зверніть увагу на вхідні файли для лр читаються у вільному форматі,
після рядка m n раціональний, лр буде шукати рівно m*n раціональних чи розділених цілих чисел
за пробілом (пусто, повернення каретки, вкладка тощо). лр не буде «скидати» зайві стовпці
введіть, якщо n менше, ніж кількість наданих стовпців.

Базовий Опції
Практично всі варіанти розміщені після кінцевий оператор, підтримуючи сумісність з CDD.
Якщо це не так, це буде чітко зазначено.

всі бази Ця опція вказує лр щоб перерахувати кожну вершину (або грань) для кожної з її основ.
Вихід Дублювання[4].[5] Цей параметр часто поєднується з printcobasis.

пов'язаний x Використовуйте з H-представництвом - для lrs або nash Або максимізувати або мінімізувати
слід вибрати варіант. x — ціле чи раціональне число. Для максимізації (відп.
мінімізація) дерево зворотного пошуку обрізається щоразу, коли поточне значення цілі
менше (відповідно більше) ніж x.

cache nлр зберігає останні n словників у зворотному дереві пошуку. Це прискорює роботу
крок назад, але вимагає більше пам’яті.

відлагоджувати вихідна основа кінцева основаРоздрукуйте загадкові, але детальні сліди, словники тощо.
починаючи з #B=початкова основа і закінчуючи #B=кінцеваоснова. відлагоджувати 0 0 дає повне
прослідкувати.

цифр n розміщений перед тим починати заяву n – максимальна кількість десяткових цифр
використаний. Якщо це перевищено, програма завершує роботу з повідомленням (зазвичай це може бути
перезапущено). За замовчуванням встановлено приблизно 100 цифр. В кінці запуску з'являється повідомлення
інформує користувача про максимальний розмір цілого числа. Це може бути використано для
оптимізувати використання пам'яті та швидкість при наступних запусках (наприклад, якщо виконується оцінка).

подвійне збурення Якщо lrs виконується з опцією maximize або minimize, зворотний пошук
дерево вкорінене в оптимальну вершину для цієї функції. Якщо існує кілька оптимумів
вершин, вихід часто не буде повним. Цей варіант дає невелике збурення
мета уникнути цього. Якщо початковий словник є подвійним, видається попередження
вироджений.

Оцінки k Оцініть розмір виходу. Використовується разом з maxdepth - див
Оцінка.[6]

геометричний // Лише H-представлення або опція voronoi // З цією опцією кожен промінь є
друкується разом з вершиною, з якою вона інцидентна. Для отримання додаткової інформації див
Геометричні промені в Поради та Коментарі[5].

падінняЦя опція вмикається автоматично printcobasis , тож дивіться нижче а
спочатку опис цієї опції. Можна використовувати з printcobasis n. (Версія 4.2b) .PP Для
вхідне H-представлення, індекси всіх вхідних нерівностей, які містять вершину/промінь, що
ось-ось буде виведено. Для спрощеної грані немає нового виходу, оскільки ці індекси
вже перераховані. В іншому випадку додаткові жорсткі нерівності перераховуються після двокрапки.
.PP Для вхідного V-представлення, індекси всіх вхідних вершин/променів, які лежать на фасеті
що ось-ось буде виведено. Індекс із зірочкою вказує, що ця вершина також знаходиться в
cobasis, але не міститься в фасеті. Виникає внаслідок використовуваної операції підйому
з вхідними V-уявленнями.

#захворюваністьТе саме, що printcobasis. Входить в комплект для сумісності з cdd.

лінійність k i1i2 i ... ikВхідні дані містять k ліній у рядках i1i2i ... ikв
вхідним файлом є рівняння. Побачити Лінійності.[3]

максимальна глибина k Пошук буде скорочено на глибині k. Усі основи з глибиною менше або
буде обчислено, що дорівнює k. k — ціле невід’ємне число, і цей параметр використовується для
оцінки - див Оцінка.[6]Примітка:: Для H-уявлень променів на глибині k не буде
повідомили. Для V-уявлень фасети на глибині k не повідомлятимуться.

максимізувати a0 a1 ... ан-1 // Тільки H-представництво //

мінімізувати a0 a1 ... ан-1 // Тільки H-представництво //

Якщо використовується з lrs, початкова вершина максимізує (або мінімізує) функцію a0 + a1x1+ ...
+ an-1 xn-1. Опція dualperturb може знадобитися, щоб уникнути подвійного виродження. Див. Nash
Рівноваги і Лінійний Програмування[7]

максимальна продуктивність n Обмежує кількість створених вихідних рядків (вершин+променів або граней) до n

розум k Відстеження назад буде припинено на глибині k, для ka невід’ємного цілого числа. Це
можна використовувати для виконання зворотного пошуку на піддеревах як окремих процесах, наприклад в a
розподілене обчислювальне середовище.

негативний // Ця опція повинна стояти перед оператором begin // // Лише H-представлення
// Помилка: можна використовувати, лише якщо початок координат є вершиною багатогранника. Для задач де
вхідні дані є H-представленням виду b+Ax>=0, x>=0 (тобто всі змінні
невід'ємні, всі обмеження нерівності) не обов'язково давати невід'ємні
обмеження явно, якщо використовується невід’ємний параметр. Цей параметр не можна використовувати для
V-подання або з опцією лінійності (у цьому випадку лінійності будуть
розглядаються як нерівності). Ця опція може використовуватися з redund, але мається на увазі
обмеження невід’ємності самі не перевіряються на надмірність. Щоб перевірити все це
необхідно явно ввести обмеження невід’ємності у вхідний файл. (У вер
4.1, початок координат має бути вершиною).

printcobasis k;Змінено в lrs 4.0 Кожна k'та кобаза друкується. Якщо k опущено, то
cobasis друкується для кожної виведеної вершини/променя/фасету. Для тривалого періоду це корисно
періодично друкувати cobasis, щоб у разі потреби можна було перезапустити програму.
H-представництво: Якщо вхідним є H-представництво, кобазою є список індексів
нерівності з вхідного файлу, які визначають поточну вершину або промінь. Дивіться варіант
падіння вище для отримання додаткової інформації. Для променів також друкується кобазис. В цьому випадку
кобаза — це кобаза вершини, з якої виходить промінь. Один з індексів
позначено зірочкою, це вказує на нерівність, яку потрібно вилучити з кобазису для визначення
промінь. Як варіант, якщо всі базивикористовується параметр, усі cobases будуть роздруковані.
V-представництво: Якщо вхід є V-представленням, кобаза є списком вхідних даних
вершини/промені, які визначають поточний фасет. Дивіться варіант падіння вище для більше
інформації. Ініціювати лр з цього аспекту всі 4 індекси повинні бути подані в такому порядку
(опустіть *).

провисання друку Нове у версії 4.2; // Використання з H-представленням // lrs друкує список
індекси вхідних нерівностей, які виконуються строго для поточної вершини, тобто.
відповідна змінна слабкості позитивна. Якщо встановлено невід’ємний, список також буде
включають індекси n+i для кожної змінної рішення xi, яка є позитивною. проект Використаний
Ірсфур'єтільки [8].

перезапуск V# R# B# глибина {фасет #s or вершина/промінь #s} Змінено в lrs4.0 лр може бути
перезапущено з будь-якого відомого cobasis. Розрахунок продовжиться до звичайного завершення. всі
інформації міститься у виводі a printcobasis варіант. порядок of
індекси is дуже важливо, введіть їх точно так, як вони відображаються у виводі з
раніше перерваний запуск.

починаючикобазис i1i2i ... в-1 Це дозволяє користувачеві вказати відому базу для
початок зворотного пошуку. i1i2i ... в-1 являє собою список нерівностей (для
H-представлення) або вершини/промені (для V-представлення), які визначають кобазис. Якщо це
недійсний, або цей параметр не вказано, лр знайде власну вихідну базу. The
дерево зворотного пошуку обрізається (обрізається) щоразу, коли зустрічається нова вершина. Примітка: це
note обов'язково породжує множину всіх вершин, суміжних з оптимальною вершиною в
багатогранник, але лише їх підмножина.

докладнийРоздрукуйте трохи більш детальну інформацію про пробіг.

обсяг // Тільки V-представлення // Обчислюємо обсяг - див. розділ Об'єм Обчислення.[9]

вороної // Тільки V-представлення - місце відразу після закінчення оператора // Обчислення
Діаграма Вороного - див. розділ Вороного діаграми.[10]

ПРИМІТКИ

1. Сторінка FAQ
http://www.ifor.math.ethz.ch/staff/fukuda/polyfaq/polyfaq.html

2. cdd
http://www.cs.mcgill.ca/%7Efukuda/soft/cdd_home/cdd.html

3. лінійності
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linearities

4. Дублювання вихідних даних
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Output%20Duplication

5.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Hints%20and%20Comments

6. Оцінка.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Estimation

7. Лінійне програмування
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linear%20Programming

8. Ірсфур'є
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#fourier

9. Розрахунок обсягу.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20Computation

10. Діаграми Вороного.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Voronoi%20Діаграми

Використовуйте lrs онлайн за допомогою служб onworks.net