lrsfouier - Online sa Cloud

PROGRAMA:

NAME

lrslib - I-convert sa pagitan ng mga pag-reset ng convex polyhedra.

SINOPSIS

Lrs input.ine

Lrs input.ine | lrsbuffer

lrsfouier file.ine [fileout]

redund input.ine

DESCRIPTION

Ang polyhedron ay maaaring ilarawan sa pamamagitan ng isang listahan ng mga hindi pagkakapantay-pantay (H-representasyon) o bilang sa pamamagitan ng isang listahan
ng mga vertex at matinding sinag nito (V-representasyon). Lrs ay isang C program na nagko-convert ng a
H-representasyon ng isang polyhedron sa V-representasyon nito, at vice versa. Ang mga problemang ito
ay kilala ayon sa pagkakabanggit sa kaitaasan enumeration at kukob katawan ng barko problema.

kay Fukuda FAQ pahina[1] ay naglalaman ng mas detalyadong panimula sa problema, kasama ng
maraming kapaki-pakinabang na tip para sa bagong user.

lrsbuffer maaaring mag-alis ng ilang duplicate na output. redund nakakahanap ng kalabisan na hindi pagkakapantay-pantay sa
input.

FILE FORMATS

Ang mga format ng file ay binuo kasama ng Komei Fukuda at tugma sa cdd[2].

Ang input para sa Lrs ay isang H- o V- representasyon ng isang polytope.

pangalan
{linya ng representasyon}
{options}
{mga linearidad[3]}
simulan
mn makatwiran
{input matrix}
dulo
{options}

pangalan ay isang pangalan na ibinigay ng gumagamit para sa polytope. Maaaring lumabas ang mga komento bago magsimula o
pagkatapos ng pagtatapos, at upang maiwasan ang interpretasyon bilang isang opsyon, dapat magsimula sa isang espesyal
character tulad ng "*" o "#".

pangalan ay isang pangalan na ibinigay ng gumagamit para sa polytope. pagkatawan linya ay alinman
"H-representasyon" o "V-representasyon". Kung aalisin, ang H-representasyon ay ipinapalagay. Ang
Ang mga input coefficient ay binabasa sa libreng format, at hindi sinusuri para sa uri. Ang mga coefficient ay
pinaghihiwalay ng puting espasyo. m ay ang bilang ng mga row at n ang bilang ng mga column ng input
matris.

H-representasyon
Ang integer m ay ang bilang ng mga hindi pagkakapantay-pantay, at ang integer n ay ang dimensyon ng
input +1. Ang isang listahan ng mga hindi pagkakapantay-pantay ay naglalaman ng mga koepisyent ng mga hindi pagkakapantay-pantay ng anyo

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

Ang hindi pagkakapantay-pantay na ito ay input bilang linya

a0 a1... an-1

Ang mga coefficient ay maaaring ipasok bilang mga integer o rational sa format na x/y.

V-representasyon
Ang integer m ay ang bilang ng mga vertices at ray, at ang integer n ay ang dimensyon ng
ang input +1. Ang bawat vertex ay ibinibigay sa form

1 v0 v 1... vn-1

Ang bawat sinag ay ibinibigay sa anyo

0 r0 r 1... rn-1

kung saan ang r0 r 1... rn-1ay isang punto sa sinag.

Dapat mayroong kahit isang vertex sa bawat file. Para sa bounded polyhedra magkakaroon ng no
pumasok ang sinag. Ang mga coefficient ay maaaring ipasok bilang mga integer o rational sa format na x/y.

nota para cdd gumagamit: Lrs gumagamit talaga ng parehong format ng file bilang cdd. Mga file na inihanda para sa
cdd dapat gumana nang kaunti o walang pagbabago. Tandaan na ang V-representasyon
tumutugma sa "hull" na opsyon sa cdd. Mga opsyon na partikular sa cdd maaaring iwan sa input
mga file at hindi papansinin ng Lrs. Tandaan ang mga input file para sa Lrs ay binabasa sa libreng format,
pagkatapos ng linya m n may talino, Lrs hahanapin ang eksaktong m*n rational o integer na pinaghihiwalay
sa pamamagitan ng puting espasyo (blangko, pagbabalik ng karwahe, tab atbp.). Lrs hindi "mag-drop" ng mga karagdagang column ng
input kung ang n ay mas mababa sa bilang ng mga column na ibinigay.

Basic Options
Halos lahat ng mga pagpipilian ay inilagay pagkatapos ang huling pahayag, pinapanatili ang pagiging tugma sa cdd.
Kung saan hindi ito ang kaso, tahasan itong babanggitin.

lahat ng base Ang pagpipiliang ito ay nagtuturo Lrs upang ilista ang bawat vertex (o facet) para sa bawat base nito.
Pagbubuhos Pagdoble[4].[5] Ang pagpipiliang ito ay madalas na pinagsama sa printcobasis.

nakatali x Gamitin kasama ang H-representation - para sa lrs o nash Alinman sa maximize o minimize
dapat piliin ang opsyon. Ang x ay isang integer o rational. Para sa pag-maximize (resp.
minimization) ang reverse search tree ay pinuputol sa tuwing ang kasalukuyang layunin na halaga
ay mas mababa (resp. higit pa) kaysa sa x.

cache nLrs nag-iimbak ng pinakabagong mga n diksyunaryo sa reverse search tree. Bumibilis ito
ang backtracking na hakbang, ngunit nangangailangan ng higit na memorya.

mag-alis ng mga insekto panimulang batayan batayan ng pagtataposMag-print ng misteryoso ngunit detalyadong bakas, mga diksyunaryo atbp.
simula sa #B=startingbasis at nagtatapos sa #B=endingbasis. mag-alis ng mga insekto 0 0 nagbibigay ng kumpletong
trace.

numero n nakalagay bago ang simulan pahayag n ay ang maximum na bilang ng mga decimal na digit
ginamit. Kung ito ay lumampas ang programa ay nagtatapos sa isang mensahe (ito ay karaniwang
na-restart). Ang default ay nakatakda sa humigit-kumulang 100 digit. Sa dulo ng isang run isang mensahe ay
ibinigay na nagpapaalam sa gumagamit ng maximum na laki ng integer na nakatagpo. Maaaring ito ay ginagamit upang
i-optimize ang paggamit ng memorya at bilis sa mga kasunod na pagtakbo (kung gumagawa ng pagtatantya halimbawa).

dualperturb Kung ang lrs ay naisakatuparan gamit ang pagpipiliang i-maximize o i-minimize, ang reverse search
puno ay nakaugat sa pinakamainam na vertex para sa function na ito. Kung mayroong mulitiple optimum
vertices, kadalasang hindi kumpleto ang output. Ang pagpipiliang ito ay nagbibigay ng isang maliit na kaguluhan sa
layunin upang maiwasan ito. Ang isang mensahe ng babala ay ibinibigay kung ang panimulang diksyunaryo ay dalawahan
lumala

mga pagtatantya k Tantyahin ang laki ng output. Ginamit kasabay ng maxdepth - tingnan
Pagtataya.[6]

geometriko // H-representation o voronoi na opsyon lamang // Sa opsyong ito, ang bawat ray ay
naka-print kasama ang vertex kung saan ito ay insidente. Para sa karagdagang impormasyon tingnan
Geometric Rays sa Hint at Comments[5].

saklawAwtomatikong bubukas ang opsyong ito printcobasis , kaya tingnan sa ibaba para sa a
paglalarawan muna ng opsyong ito. Maaaring gamitin sa printcobasis n. (Ver 4.2b) .PP Para sa
input H-representation, mga indeks ng lahat ng input na hindi pagkakapantay-pantay na naglalaman ng vertex/ray na
ay malapit nang maging output. Para sa isang simpleng mukha, walang bagong output, dahil ang mga indeks na ito
ay nakalista na. Kung hindi, ang mga karagdagang mahigpit na hindi pagkakapantay-pantay ay nakalista pagkatapos ng isang colon.
.PP Para sa input V-representation, mga indeks ng lahat ng input vertices/ray na nasa facet
malapit na itong maging output. Ang naka-star na index ay nagsasaad na ang vertex na ito ay nasa
cobasis, ngunit hindi nakapaloob sa facet. Lumilitaw ito dahil sa ginamit na operasyon ng pag-aangat
na may mga input na V-representasyon.

#insidenteKapareho ng printcobasis. Kasama para sa pagiging tugma sa cdd.

linearity k i1i2 i ... ikAng input ay naglalaman ng mga k linearity sa mga hilera i1i2i ... ikng
Ang input file ay mga equation. Tingnan mo Mga linearidad.[3]

maxdepth k Ang paghahanap ay puputulin sa lalim k. Lahat ng mga base na may lalim na mas mababa sa o
katumbas ng k ay kukuwentahin. k ay isang hindi negatibong integer, at ang opsyong ito ay ginagamit para sa
mga pagtatantya - tingnan Pagtataya.[6]nota: Para sa mga H-representasyon, ang mga sinag sa lalim k ay hindi magiging
iniulat. Para sa mga V-representasyon, hindi iuulat ang mga facet sa depth k.

maximize a0 a1 ... isang-1 // H-representasyon lamang //

mabawasan a0 a1 ... isang-1 // H-representasyon lamang //

Kung ginamit sa lrs ang panimulang vertex ay nagma-maximize (o nagpapaliit) sa function na a0 + a1x1+ ...
+ an-1 xn-1. Maaaring kailanganin ang opsyong dualperturb para maiwasan ang dual degeneracy.Tingnan ang Nash
Equilibria at Linear Programming[7]

maxoutput n Nililimitahan ang bilang ng mga linya ng output na ginawa (alinman sa mga vertices+ray o facet) sa n

kaisipan k Ang backtracking ay wawakasan sa lalim k, para sa ka non-negative integer. Ito
ay maaaring gamitin para sa pagpapatakbo ng reverse search sa mga subtree bilang magkahiwalay na proseso, hal sa a
distributed computing environment.

hindi negatibo // Ang opsyon na ito ay dapat na mauna bago ang begin statement// //H-representation lang
// Bug: Magagamit lang kung ang pinagmulan ay isang vertex ng polyhedron Para sa mga problema kung saan
ang input ay isang H-representasyon ng form b+Ax>=0, x>=0 (ibig sabihin, lahat ng variable
hindi-negatibo, lahat ng mga hadlang ay hindi pagkakapantay-pantay) hindi kinakailangang ibigay ang di-negatibo
tahasan ang mga hadlang kung gagamitin ang nonnegative na opsyon. Hindi magagamit ang opsyong ito para sa
V-representasyon, o kasama ang linearity na opsyon (kung saan ang mga linearity ay magiging
itinuturing na hindi pagkakapantay-pantay). Maaaring gamitin ang opsyong ito sa redund , ngunit ang ipinahiwatig
Ang nonnegativity constraints ay hindi sinusuri sa kanilang sarili para sa redundancy. Upang subukan ang lahat ng ito
ay kinakailangan upang ipasok ang mga nonnegativity constraints nang tahasan sa input file. (Sa Ver
4.1, ang pinagmulan ay dapat na isang vertex).

printcobasis k;Binago sa lrs 4.0 Ang bawat k'th cobasis ay nakalimbag. Kung ang k ay tinanggal, ang
Ang cobasis ay naka-print para sa bawat vertex/ray/facet na output. Para sa isang mahabang panahon ito ay kapaki-pakinabang
upang i-print ang cobasis paminsan-minsan upang ang programa ay ma-restart kung kinakailangan.
H-representasyon: Kung ang input ay isang H-representasyon ang cobasis ay isang listahan ng mga indeks ng
ang mga hindi pagkakapantay-pantay mula sa input file na tumutukoy sa kasalukuyang vertex o ray. Tingnan ang opsyon
saklaw sa itaas para sa karagdagang impormasyon. Para sa mga sinag, ang isang cobasis ay naka-print din. Sa kasong ito
ang cobasis ay ang cobasis ng vertex kung saan nagmumula ang sinag. Isa sa mga indeks
ay naka-star, ito ay nagpapahiwatig ng hindi pagkakapantay-pantay na aalisin mula sa cobasis upang tukuyin ang
sinag. Bilang kahalili, kung ang lahat ng baseang opsyon ay ginagamit, lahat ng cobases ay ipi-print out.
V-representasyon: Kung ang input ay isang V-representasyon, ang cobasis ay isang listahan ng input
vertices /rays na tumutukoy sa kasalukuyang facet. Tingnan ang opsyon saklaw sa itaas para sa higit pa
impormasyon. Upang simulan Lrs mula sa facet na ito ang lahat ng 4 na indeks ay dapat ibigay sa ganitong pagkakasunud-sunod
(alisin ang *).

printslack Bago sa Ver 4.2 ; // Gamitin kasama ang H-representation // lrs ay nagpi-print ng listahan ng
mga indeks ng mga hindi pagkakapantay-pantay ng input na mahigpit na nasiyahan para sa kasalukuyang vertex, ibig sabihin.
Ang kaukulang slack variable ay positibo. Kung nakatakda ang nonnegative, gagawin din ng listahan
isama ang mga indeks n+i para sa bawat variable ng desisyon xi na positibo. proyekto Ginamit ni
lrsfouier[8] lamang.

i-restart ang V# R# B# lalim {facet #s or vertex/ray #s} Binago sa lrs4.0 Lrs ay maaaring maging
na-restart mula sa anumang kilalang cobasis. Ang pagkalkula ay magpapatuloy sa normal na pagwawakas. Lahat
ng impormasyon ay nakapaloob sa output mula sa a printcobasis pagpipilian Ang order of
ang mga indeks ng is napaka mahalaga, ipasok ang mga ito nang eksakto kung paano lumilitaw ang mga ito sa output mula sa
dating na-abort run.

panimulang kobasis i1i2i ... sa-1 Nagbibigay-daan ito sa user na tumukoy ng kilalang cobasis para sa
simula ng reverse search. i1i2i ... sa-1 ay isang listahan ng mga hindi pagkakapantay-pantay (para sa
H-representation) o vertices/ray (para sa V-representation) na tumutukoy sa isang cobasis. Kung ito ay
di-wasto, o hindi tinukoy ang opsyong ito, Lrs ay makakahanap ng sarili nitong panimulang cobasis. Ang
Ang reverse search tree ay pinuputol(pinutol) tuwing may makaharap na bagong vertex. Tandaan: Ito
ang tala ay kinakailangang gumawa ng set ng lahat ng vertex na katabi ng pinakamainam na vertex in
ang polyhedron, ngunit isang subset lamang ng mga ito.

pandiwangMag-print ng bahagyang mas detalyadong impormasyon tungkol sa pagtakbo.

dami // V-representation lang // Compute volume - tingnan ang seksyon Dami Pagtutuos.[9]

voronoi // V-representation lang - ilagay kaagad pagkatapos ng end statement // Compute
Voronoi diagram - tingnan ang seksyon Voronoi Mga diagram.[10]

NOTA

1. FAQ page
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. linearities
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linearities

4. Pagdoble ng Output
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. Pagtataya.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Estimation

7. Linear Programming
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Linear%20Programming

8. lrsfouier
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#fourier

9. Pagkalkula ng Dami.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Volume%20Computation

10. Mga Diagram ng Voronoi.
http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#Voronoi%20Diagrams

Gamitin ang lrsfouier online gamit ang mga serbisyo ng onworks.net